【leetcode hot 100 17】电话号码的字母组合

分析：当设计关键字“所有组合”时，要考虑深度优先遍历、广度优先遍历（层次遍历），其中：

• 深度优先搜索：

  • 自顶向下的递归实现深搜
  • 定义子问题
  • 在当前递归层结合子问题结果解决原问题

• 广度优先搜索

  • 利用队列
  • 从当前出发，逐步构造解

解法一：回溯法

class Solution {public List<String> letterCombinations(String digits) {List<String> result = new ArrayList<>();if(digits.length()==0){return result;}StringBuffer temp = new StringBuffer();  // 这里使用StringBuffer(可变，或者说变化容易)，而不是String(不可变，或者说变化困难)String[] letter = new String[]{"abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};backtrack(result, temp, letter, digits, 0); // 选择第几个数的字母return result;}public void backtrack(List<String> result, StringBuffer temp, String[] letter, String digits, int num){if(num==digits.length()){result.add(new String(temp));return;}// 找第num个数字对应的字母String str = letter[(int)(digits.charAt(num)-'0')-2];for(int i=0; i<str.length(); i++){char ch = str.charAt(i);temp.append(ch);backtrack(result, temp, letter, digits, num+1);temp.deleteCharAt(num);}}
}

注意：

• temp使用StringBuffer(可变，或者说变化容易)，而不是String(不可变，或者说变化困难)
• char转换为int：(int)(digits.charAt(num)-'0')
• 应对digits=""：if(digits.length()==0){return result;}
• 对于StringBuffer，函数temp.append(ch)为加入元素ch；函数temp.deleteCharAt(num)为删除位置为num的元素；函数temp.delete(n,m)为删除字符串[n,m)的元素。