Letter Combination of a Phone Number

Problem: Letter Combination of a Phone Number

To solve this problem, we can simply establish a dictionary to store relationship between digits and numbers. Then we scan the digits from the first one and append all possible letters to current strings. After we finish scanning all digits, we add string results to our answer.

Code in Python:

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits: return []
        dict = {"2":["a","b","c"], "3":["d","e","f"], "4":["g","h","i"],"5":["j","k","l"],"6":["m","n","o"],"7":["p","q","r","s"],"8":["t","u","v"],"9":["w","x","y","z"]}
        ans = []
        def combine(pos, s):
            if pos == len(digits):
                ans.append(s)
                return
            for c in dict[digits[pos]]:
                combine(pos+1, s+c)
        combine(0, "")
        return ans

Code in Java:

public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0)
            return new ArrayList<String>();

        HashMap<Character, String> hm = new HashMap<Character, String>();
        hm.put('2', "abc");
        hm.put('3', "def");
        hm.put('4', "ghi");
        hm.put('5', "jkl");
        hm.put('6', "mno");
        hm.put('7', "pqrs");
        hm.put('8', "tuv");
        hm.put('9', "wxyz");

        LinkedList<String> res = new LinkedList<String>();
        res.add(String.valueOf(""));
        for (int i = 0; i < digits.length(); i++) {
            String chars = hm.get(digits.charAt(i));
            int listSize = res.size();
            for (int j = 0; j < listSize; j++) {
                String s = res.poll();
                for (int k = 0; k < chars.length(); k++) {
                    res.add(s+String.valueOf(chars.charAt(k)));
                }
            }
        }
        return res;
    }
}