LeetCode-Letter Combinations of a Phone Number

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

在最开始，我考虑使用非常复杂的 Map<Character,List> 来表示电话号码键盘，但是觉得没必要，改成了一个很简单的二维数组，程序的压力就小了很多。

之后，在计算重复值的时候避免了使用递归一层一层地添加值，而使用了一个二重循环通过几个字母的间隔规律来填写，应该也会比较快。

但是为了完成这些，就需要先计算出来返回 List 的长度，不过在长度不长的情况下，循环并不会消耗多少时间。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ret=new ArrayList<>();
        char[] digs=digits.toCharArray();
        if(digs.length==0) return ret;
        char[][] d2lArr={
            {'a','b','c'},
            {'d','e','f'},
            {'g','h','i'},
            {'j','k','l'},
            {'m','n','o'},
            {'p','q','r','s'},
            {'t','u','v'},
            {'w','x','y','z'}
        };
        int[] lenArr=new int[digs.length];
        int allLen=1;
        for(int i=0;i<digs.length;i++){
            int l=d2lArr[digs[i]-48-2].length;
            lenArr[i]=l;
            allLen*=l;
        }
        StringBuilder[] sbArr=new StringBuilder[allLen];
        for(int j=0;j<digs.length;j++){
            int gap=1,now=0,id=0;
            for(int k=j+1;k<digs.length;k++) gap*=lenArr[k];
            for(int m=0;m<sbArr.length;m++){
                if(sbArr[m]==null) sbArr[m]=new StringBuilder();
                sbArr[m].append(d2lArr[digs[j]-48-2][id%d2lArr[digs[j]-48-2].length]);
                if(++now==gap){
                    now=0;
                    id++;
                }
            }
        }
        for(StringBuilder sb:sbArr){
            ret.add(sb.toString());
        }
        return ret;
    }
}

不知道为啥就 Beats 了 100%的 Submission。

看了一下 别人的博客 ，大受启发，居然还有很多办法来解决。

第一种办法是定义一种新的 List 相乘的运算，不断让新的 List 乘进去扩充原 List,非常实用。

不过，之前所使用的 char 类型数组已经不是很好用了（除非用一大堆的 StringBuilder），所以直接将它的类型转换为 String 了。

class Solution {
    public List<String> combination(List<String> ls1, List<String> ls2){
        if(ls1.isEmpty()) return ls2;
        List<String> ls=new ArrayList<>();
        for(int i=0;i<ls1.size();i++){
            for(int j=0;j<ls2.size();j++){
                ls.add(ls1.get(i)+ls2.get(j));
            }
        }
        return ls;
    }
    public List<String> letterCombinations(String digits) {
        String[][] d2lArr={
            {"a","b","c"},
            {"d","e","f"},
            {"g","h","i"},
            {"j","k","l"},
            {"m","n","o"},
            {"p","q","r","s"},
            {"t","u","v"},
            {"w","x","y","z"}
        };
        List<String> ret=new ArrayList<>();
        char[] digs=digits.toCharArray();
        if(digs.length==0) return ret;
        for(char d:digs)
            ret=combination(ret,Arrays.asList(d2lArr[d-48-2]));
        return ret;
    }
}

第二种办法是实用队列。这是一种非常神奇的办法！

首先，LinkedList 不仅实现了 List 的接口，还实现了 Deque 接口，所以虽然 LinkedList 是序列，但是它可以作为队列使用。

然后，程序中巧妙地使用入队和出队来解决问题。在 for 循环的每一轮中，上一次入队的字符将依次出队，和后面的字符组合，然后再入队。这样，队列中的字符就可以不断增长。

另外，在 for 循环之前 add 一个空字符串以及使用 peek 方法查看长度来控制循环条件，都十分的精妙。

class Solution {
    public List<String> letterCombinations(String digits) {
        String[][] d2lArr={
            {"a","b","c"},
            {"d","e","f"},
            {"g","h","i"},
            {"j","k","l"},
            {"m","n","o"},
            {"p","q","r","s"},
            {"t","u","v"},
            {"w","x","y","z"}
        };
        LinkedList<String> ret=new LinkedList<>();
        char[] digs=digits.toCharArray();
        if(digs.length==0) return ret;
        ret.add("");
        for(int i=0;i<digs.length;i++){
            String[] sArr=d2lArr[digs[i]-48-2];
            while(ret.peek().length()==i){
                String t=ret.remove();
                for(String s:sArr) ret.add(t+s);
            }
        }
        return ret;
    }
}

最后一种办法是常规的递归方式，主要是需要有一个变量 pos 来控制增加字符的位置。

class Solution {
    public final static String[][] d2lArr={
        {"a","b","c"},
        {"d","e","f"},
        {"g","h","i"},
        {"j","k","l"},
        {"m","n","o"},
        {"p","q","r","s"},
        {"t","u","v"},
        {"w","x","y","z"}
    };
    public void comb(char[] digs, int pos, List<String> ret, String prefix){
        if(pos==digs.length){
            ret.add(prefix);
            return;
        }
        String[] sArr=d2lArr[digs[pos]-48-2];
        for(String s:sArr) comb(digs,pos+1,ret,prefix+s);
    }
    public List<String> letterCombinations(String digits) {
        List<String> ret=new ArrayList<>();
        char[] digs=digits.toCharArray();
        if(digs.length==0) return ret;
        comb(digs,0,ret,"");
        return ret;
    }
}