回溯 01

---

LeetCode 17

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

解题思路

17解题思路

本题回溯没有不符合的条件，只要递归到头了直接原路返回的结果都可以。

依次取“电话号码”，当前电话号码对应的字符串再依次构成子树。
接下来的号码对应的字符串再衔接上去，直到号码遍历结束，即可把字符串原路返回。

代码如下

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<String>();
        if (digits.length() == 0) {
            return ans;
        }
        Map<Character, String> map = new HashMap<Character, String>();  // 哈希表存储号码对应的字符串
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        backtrack(ans, map, digits, 0, new StringBuffer());
        return ans;

    }
    
    // 回溯算法
    public void backtrack(List<String> ans, Map<Character, String> map, String digits, int index,
            StringBuffer stringBuffer) {
        // index是当前遍历到的号码位置，从0开始，如果递归到头了，就将存在stringBuffer的串存进结果里
        if (index == digits.length()) {     
            ans.add(stringBuffer.toString());
        } else {
            char charAt = digits.charAt(index);
            String curString = map.get(charAt);
            // 将当前号码对应的串，依次添加到子树中
            for (int i = 0; i < curString.length(); i++) {
                stringBuffer.append(curString.charAt(i));
                backtrack(ans, map, digits, index + 1, stringBuffer);   // 继续遍历下一位号码
                // 到末尾时会把所有存在stringBuffer的存入结果中，要在回溯过程中把原来重复的字符删掉
                stringBuffer.deleteCharAt(index);   
            }
        }
    }

//  public static void main(String[] args) {
//      Solution k = new Solution();
//      String a = "23";
//      List<String> l = new ArrayList<String>();
//      l = k.letterCombinations(a);
//      System.out.println(l.toString());
//  }
}