17.电话号码的字母组合
题目链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
难度：中等
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解法一：普通的循环(类似于建树的BFS广度优先搜索，层序遍历)
首先建立手机按键与字符的对应关系，利用Map存储。
我们可以利用遍历digits的每一个字符，依次把当前数字对应的字符串添加到最终的list集合。
每一拿到一个数字按键，拿到按键对应的字符串s，
将当前的list集合和字符串按照笛卡尔积的形式拼接，组合形成新的list。
然后将list返回，进行下一个按键的拼接。
循环结束，返回结果字符串集合。
缺点：时间复杂度为O(n^3)
时间复杂度较高，完成leetcode上面的测试需要7ms。
代码：
public List<String> addLetter(List<String> list, String s) {
List<String> newList = new ArrayList<String>();
for (int j = 0; j < list.size(); j++) {
for (int i = 0; i < s.length(); i++) {
newList.add(list.get(j) + s.charAt(i));
}
}
return newList;
}
public List<String> letterCombinations(String digits) {
HashMap<String, String> map = new HashMap<>();
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");
List<String> result = new ArrayList<>();
if (digits.length() == 0) {
return result;
}
result.add("");
for (int i = 0; i < digits.length(); i++) {
result = addLetter(result, map.get(String.valueOf(digits.charAt(i))));
}
return result;
}
解法二：回溯法(类似于建树的DFS深度优先搜索，深度搜索)
首先建立手机按键与字符的对应关系，利用Map存储。
我们先建立一个空字符串letter,来临时存储组合的结果字符串
我们利用递归，拿出digits中的第一个按键对应的字符串，
然后遍历字符串中的每一个字符，与当前的字符串letter连接，
连接后，我们直接递归去找下一个按键，依次拼接
最终，当没有新的按键输入，那么当前的字符串letter就是最终字符串，（这也是递归结束的条件，递归的出口）
将其保存到最终的集合result中，再依次递归
退出递归后，得到的集合result就是最终结果。
时间复杂度：表面看上去类似于 O(n)。但是如果细究的话肯定不止O(n)。
Leetcode测试案例，运行时间只需要1ms
代码：
Map<String, String> phoneMap = new HashMap<String, String>() {
{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}
};
List<String> result = new ArrayList<>();
public void addLetter2(String letter, String nextLetter) {
if (nextLetter.length() == 0) {
result.add(letter);
} else {
String digit = String.valueOf(nextLetter.charAt(0));
String letters = phoneMap.get(digit);
for (int i = 0; i < letters.length(); i++) {
String c = String.valueOf(letters.charAt(i));
addLetter2(letter + c, nextLetter.substring(1));
}
}
}
public List<String> letterCombinations2(String digits) {
if (digits.length() != 0)
addLetter2("", digits);
return result;
}
