Interview Question Letter Combinations of a Phone Number

By Fatih KABAKCI

The problem is to have all letter combinations of a given digit in regard to phone keypad. The solution in Java has been provided by the member of LeetCode lirensun.

Problem #17 - Letter Combinations of a Phone Number

Description: Given a digit string, return all possible letter combinations that the number could represent.



A mapping of digit to letters (just like on the telephone buttons) is given below.

Difficulty: Medium

Solution in Java

Solution by lirensun

package com.fatihkabakci.Medium.LetterCombPhoneNumber;

import java.util.ArrayList;
import java.util.List;

/**
 * @author fkabakci
 * 
 * Problem Description: Given a digit string, return all possible letter combinations that the number could represent.
 * 
 * Input:Digit string "23"
 * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * 
 * Note:
 * Although the above answer is in lexicographical order, your answer could be in any order you want.
 * 
 * Solution by lirensun:
 * 
 * 0. Define a list to store the combination of the characters.
 * 1. Initialize the list by adding an empty value to it.
 * 2. for(i : 0 to number of digits)
 * 	  a. While(the length of the first character in the list equals to the order of digit)
 * 		  b. Use the first element of the list as prefix. Get it.
 * 		  c. By the way, do not forget to make a conversion of the digit from character format to integer.
 * 		     d. for(j : 0 to number of characters in the keypad)
 * 				 e. add prefix (section b) + character (section d) into the list.
 * 3. Return the list.
 */

public class LetterCombinationsPhoneNumber {
	final static String[] keyPad = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
	
	public List<String> letterCombinations(String digits) {
		List<String> list = new ArrayList<String>();
		if(digits == null || digits.length() == 0)
			return list;
		
		list.add("");
	    for(int i = 0; i < digits.length(); i++) {
	        while(list.get(0).length() == i) {
	            String prefix = list.remove(0);
	            int digit = digits.charAt(i) - "0";
	            for(char character : keyPad[digit].toCharArray())
	            	list.add(prefix + character);
	        }
	    }
	    return list;
    }
}