LeetCode(BackTracking)Letter Combinations of a Phone Number

2018-06-25

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

1 2	Input: "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.

思路：给定2-9的数字符，求出对应的所有字符可能情况。题目归在了回溯法这一类中，其实回溯法个人理解就是自底向上的查找，先从最小的情况入手，然后逐渐找到更多的解，最后穷举出所有的可能情况。代码如下：

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res=new ArrayList<String>();
        int dlength=digits.length();
        if(dlength==0 || digits==null){
            return res;
        }
        //定义映射字符数组
        String [] mapping={" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        res.add("");
        for(int i=0;i<dlength;i++){
            List<String> templist=new ArrayList<String>(); //暂时存储当前字符对应的所有可能结果
            char [] temp=mapping[digits.charAt(i)-'0'].toCharArray(); //根据按键选中映射数组里的字符串
            int tplength=temp.length;
            for(int j=0;j<tplength;j++){
                for(String s:res){
                    templist.add(s+temp[j]);
                }
            }
            res=templist;
            
        }
        return res;
    }
}

　　代码中有几个小技巧：1.题目说了只包含2-9的数字，我们为什么要定义一个 String [] mapping={“ “,””,”abc”,”def”,”ghi”,”jkl”,”mno”,”pqrs”,”tuv”,”wxyz”};这个数组呢，其实我们定义了0—9。其实这完全是为了能够在循环的时候，减少变量，统一下标，当我们定义了这样一个映射数组的时候，输入是几，对应的数组中的位置就是几，比如输入的数字是“2”,那么我们利用“2“-”0“=2就可以计算出”2“在字符数组中所对应的mapping[2]=”abc”；

　　2.利用了一个临时的字符数组来存储每一次大循环里产生的结果，在小循环结束后将结果集更新为当前的临时结果集。