Letter Combinations of a Phone Number

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"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Naive Way: 先初始化list，遍历String中所有字符，每经过一个都在原有的list<String>里加入新字符，把每一个新String都加入到list里，然后删除原来list长度的String。这样描述下来，貌似用一个queue来存string会更好。但是运行时间对比下来用queue反而更慢些。

下面是不用queue的。

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<String>();
        String zero = "";
        list.add(zero);
        for(int i = 0;i < digits.length();i++){
            String chars = digit2chars(digits.charAt(i));
                int preLen = list.size();
                for(int t = 0;t < preLen;t++){
                    for(int j = 0;j < chars.length();j++){
                        String s = new String(list.get(t)+chars.charAt(j));
                        list.add(s);
                    }
                }
                for(int t = 0;t < preLen;t++){
                    list.remove(0);
                }
        }
        return list;
    }
    
    private String digit2chars(char num){
        switch(num){
            case '1':
                return "";
            case '2':
                return "abc";
            case '3':
                return "def";
            case '4':
                return "ghi";
            case '5':
                return "jkl";
            case '6':
                return "mno";
            case '7':
                return "pqrs";
            case '8':
                return "tuv";
            case '9':
                return "wxyz";
            default:
                return "";
        }
    }
}


下面是用queue的。

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<String>();
        Queue<String> queue = new LinkedList<String>();
        String empty = "";
        queue.add(empty);
        for(int i = 0;i < digits.length();i++){
            String chars = digit2chars(digits.charAt(i));
                int preLen = queue.size();
                for(int t = 0;t < preLen;t++){
                    String pre = queue.poll();
                    for(int j = 0;j < chars.length();j++){
                        String s = new String(pre+chars.charAt(j));
                        queue.add(s);
                    }
                }
        }
        list.addAll(queue);
        return list;
    }
}