Letter Combinations of a Phone Number

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.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

图例

分析

和subset 问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母，并加入当前combination中传到下一层递归。

1. We traverse through the digit string and for each digit(like "2" in this example), we get the character string(a,b,c) associated append it to the all the values
2. we use path to update each path's result, while incrementing counter named current
3. once digits' length equals to current counter, we add this path into result.

代码

//Time: O(4 ^n)
 Space: O(n)
class Solution {
    private static String[] keyboard =
            new String[]{ " ", "", "abc", "def", // '0','1','2',...
            "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    public List<String> letterCombinations(String digits) {  // “23”
        List<String> result = new ArrayList<>();
        if(digits.length()==0) return result;
        dfs(digits, 0,"",result);
        return result; 
    }

    private void dfs(String digits, int current, String path, List<String> result){
        if(digits.length()==current){
            result.add(path);
            return;
        }

        String s = keyboard[digits.charAt(current) -'0'];

        for(char c: s.toCharArray()){
            dfs (digits, current+1, path+c, result);
        }    
    }
}