LeetCode_17

• 题意以及限制条件
• 想到的所有可能解法
• 对应的代码
• 测试样例

题意以及限制条件

1. 题目：

2. 限制条件：
   

想到的所有可能解法

• Ways_1——回溯

  0. 时间复杂度——O( 3 m 3^m 3m X 4 n 4^n 4n)，其中 m 是输入中对应 3个字母的数字个数（包括数字 2、3、4、5、6、8），n是输入中对应 4个字母的数字个数（包括数字 7、9）；
  1. 空间复杂度——O(m + n)，m+n是输入数字的总个数。

对应的代码

• Ways_1

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<String>();
        //if Input is "",digits.length() == 0 can help return the right answer.
        if(digits == null || digits.length() == 0) return list;
        String[] map = new String[] {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        backtrack(digits,list,map,new StringBuilder(),0);
        return list;
    }

    private static void backtrack(String digits, List<String> list, String[] map, StringBuilder sb, int start) {
        if (start == digits.length()) {
            // list.add(new String(sb));
            list.add(sb.toString());
            return;
        }
        int index = digits.charAt(start) - '0';
        for (int i = 0; i < map[index].length(); ++i) {
            sb.append(map[index].charAt(i));
            backtrack(digits, list, map, sb, start + 1);
            // sb.deleteCharAt(sb.length() - 1);
            sb.setLength(sb.length() - 1);
        }
    }
}

测试样例