Letter Combinations of a Phone Numer – Leetcode #17

This problem is from Leetcode. The problem statement in short is given below:

Given a string of digits from 2 to 9, return all possible letter combinations that the number could represent, based on the classic phone keypad mapping.

SOLUTION

FIRST APPROACH

Lets make a table for input = 23

Step 1 - process digit 2

PREVIOUS COMBO                 LETTERS FOR '2'                   NEW COMBINATIONS
    ""                          a, b, c                           [a, b, c]



Step 2 - process digit 3

PREVIOUS COMBO                 LETTERS FOR '3'                   NEW COMBINATIONS
    a                           d, e, f                           [ad, ae, af]

    b                           d, e, f                           [bd, be, bf]

    c                           d, e, f                           [cd, ce, cf]

See the code sample below :

public List<String> letterCombinations(String digits) {

		List<String> tempList = new ArrayList<String>();
		List<String> combinationsList = new ArrayList<String>();

		String[] phoneMap = {
				"",     "",     "abc", "def", "ghi",
				"jkl",  "mno",  "pqrs", "tuv", "wxyz"
		};

		for(int i=0; i<digits.length(); i++) {
			
			// extract digits one by one
			Integer curDigit = Integer.parseInt(String.valueOf(digits.charAt(i)));
			
			// get the corresponding string from phoneMap
			String str = phoneMap[curDigit];
			
			// add the chars to the list
			if(combinationsList.isEmpty()) {
				for(int j=0; j<str.length(); j++) {

					combinationsList.add(String.valueOf(str.charAt(j)));				

				}				 
			}
			else {
				
				// now build out the combinations
				Iterator<String> iter = combinationsList.iterator();
				while(iter.hasNext()) {

					String curChar = (String)iter.next();

					for(int k=0; k<str.length(); k++) {

						String repl = curChar+String.valueOf(str.charAt(k));
						tempList.add(repl);
					}
					
				}// endWhile

				combinationsList.clear();
				combinationsList.addAll(tempList);
				tempList.clear();

			}		 
		}	 
		return combinationsList;
	}

You can checkout the code from Github here – Letter Combinations of a Phone Numer – Leetcode #17

PERFORMANCE

RUNTIME	1 ms | Beats 53.60 %
MEMORY	42.04 MB | Beats 78.35 %
TIME COMPLEXITY	O (4N)
SPACE COMPLEXITY	O (4N)