hot100-17 电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路

深度优先DFS
广度优先BFS（借助辅助队列）
循环
递归

代码

class Solution {
    /**
    //BFS
    public List<String> letterCombinations(String digits) {
        if(digits==null || digits.length()==0) {
            return new ArrayList<String>();
        }
        //一个映射表，第二个位置是"abc“,第三个位置是"def"。。。
        //这里也可以用map，用数组可以更节省点内存
        String[] letter_map = {
            " ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
        };
        List<String> res = new ArrayList<>();
        //先往队列中加入一个空字符
        res.add("");

        //首先往队列中依次放入a,b,c，然后将d、e、f逐个拼接到a,b,c的后面

        for(int i=0;i<digits.length();i++) {
            //由当前遍历到的字符，取字典表中查找对应的字符串
            String letters = letter_map[digits.charAt(i)-'0'];
            int size = res.size();
            //计算出队列长度后，将队列中的每个元素挨个拿出来
            for(int j=0;j<size;j++) {
                //每次都从队列中拿出第一个元素
                String tmp = res.remove(0);
                //然后跟"def"这样的字符串拼接，并再次放到队列中
                for(int k=0;k<letters.length();k++) {
                    res.add(tmp+letters.charAt(k));
                }
            }
        }
        return res;
    }
    **/
    //DFS
    private List<String> ans = new ArrayList<>();
    private Map<Character, char[]> charToCharMap;
    private int deep;
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0){
            return ans;
        }

        this.deep = digits.length();

        initcharToCharMap();

        helper(new StringBuilder(), digits, 0);

        return ans;
    }

    private void initcharToCharMap(){
        charToCharMap = new HashMap<>();
        charToCharMap.put('2', new char[]{'a', 'b', 'c'});
        charToCharMap.put('3', new char[]{'d', 'e', 'f'});
        charToCharMap.put('4', new char[]{'g', 'h', 'i'});
        charToCharMap.put('5', new char[]{'j', 'k', 'l'});
        charToCharMap.put('6', new char[]{'m', 'n', 'o'});
        charToCharMap.put('7', new char[]{'p', 'q', 'r', 's'});
        charToCharMap.put('8', new char[]{'t', 'u', 'v'});
        charToCharMap.put('9', new char[]{'w', 'x', 'y', 'z'});
    }

    private void helper(StringBuilder builder, String digits, int index){
        if(index == deep){
            ans.add(builder.toString());
            return;
        }

        char[] arr = charToCharMap.get(digits.charAt(index));
        for(char c: arr){
            builder.append(c);
            helper(builder, digits, index+1);
            builder.deleteCharAt(builder.length()-1);   //每次清除最后一个连接的字母，相当于回归递归之前的状态
        }
    }
}

附：如何理解并编写递归？

一般方法:一般情况+简单用例
思想:数学归纳法

记住，不要想着用回溯和迭代去理解递归，那不是正确的方法。

在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中, 因为回溯就像反过来思考迭代, 这是我们习惯的思维方式, 但是实际上递归不需要这样来验证. 比如, 另外一个常见的例子是阶乘的计算. 阶乘的定义: “一个正整数的阶乘（英语：factorial）是所有小于或等于该数的正整数的积，并且0的阶乘为1。” 以下是Ruby的实现:

def (n)
    if n <= 1 then
        return 1
    else
        return n * factorial(n - 1)
    end
end

用回溯的方式思考虽然可以验证当n = 某个较小数值是否正确, 但是其实无益于理解.

Paul Graham提到一种方法, 该方法如下:

当n=0, 1的时候, 结果正确.

假设函数对于n是正确的, 函数对n+1结果也正确.如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。

这种方法很像数学归纳法, 也是递归正确的思考方式, 事实上, 阶乘的递归表达方式就是1!=1，n!=(n-1)!×n(见wiki). 当程序实现符合算法描述的时候, 程序自然对了, 假如还不对, 那是算法本身错了…… 相对来说, n, n+1的情况为通用情况, 虽然比较复杂, 但是还能理解, 最重要的, 也是最容易被新手忽略的问题在于第1点, 也就是基本用例(base case)要对. 比如, 上例中, 我们去掉if n <= 1的判断后, 代码会进入死循环, 永远不会结束.

上面讲了怎么理解递归是正确的, 同时可以看到在有递归算法描述后, 其实程序很容易写. 那么最关键的问题就是, 我们怎么找到一个问题的递归算法呢?

你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题.

你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例).如果这两件事完成了, 那问题就解决了. 因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决.

现在我们用这个方法来寻找汉诺塔这个游戏的解决方法.(这其实是数学家发明的游戏)

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

每次只能移动一个圆盘.

大盘不能叠在小盘上面.

现在我们来应用Paul Graham的方法思考这个游戏.

一般情况:

当有N个圆盘在A上, 我们已经找到办法将其移到C杠上了,我们怎么移动N+1个圆盘到C杠上呢?

很简单, 我们首先用将N个圆盘移动到C上的方法将N个圆盘都移动到B上, 然后再把第N+1个圆盘(最后一个)移动到C上, 再用同样的方法将在B杠上的N个圆盘移动到C上. 问题解决.

基本用例:

当有1个圆盘在A上, 我们直接把圆盘移动到C上即可.

算法描述大概就是上面这样了, 其实也可以看作思维的过程, 相对来说还是比较自然的. 下面是Ruby解:

def hanoi(n, from, to, other)
    if n == 1 then
        puts from + ' -> ' + to
    else
        hanoi(n-1, from, other, to)
        hanoi(1, from, to, other)
        hanoi(n-1, other, to, from)
    end
end