博文中会简要介绍Leetcode P0017题目分析及解题思路。
“Letter Combinations of a Phone Number”是典型的深度搜索的题目，这里是溯洄法，核心其实就是在考察深度搜索（DFS）
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.
简单来说，DFS的核心就在于递归搜索，每次搜索一个分支到最深一层，然后向上回溯直到出现还没有搜索过的分支，停止向上回溯后，在停留的结点位置随机选择一条还没有探索的分支，重复上述操作，直到所有的分支都已经探索完成。
以下是Java的题解代码实现。
class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0)
return new ArrayList<>();
Map<Character, List<String>> digit2LettersMap = new HashMap<>();
digit2LettersMap.put('1', new ArrayList<>());
digit2LettersMap.put('2', Arrays.asList(new String[] {"a", "b", "c"}));
digit2LettersMap.put('3', Arrays.asList(new String[] {"d", "e", "f"}));
digit2LettersMap.put('4', Arrays.asList(new String[] {"g", "h", "i"}));
digit2LettersMap.put('5', Arrays.asList(new String[] {"j", "k", "l"}));
digit2LettersMap.put('6', Arrays.asList(new String[] {"m", "n", "o"}));
digit2LettersMap.put('7', Arrays.asList(new String[] {"p", "q", "r", "s"}));
digit2LettersMap.put('8', Arrays.asList(new String[] {"t", "u", "v"}));
digit2LettersMap.put('9', Arrays.asList(new String[] {"w", "x", "y", "z"}));
this.combine(digits.toCharArray(), 0, new StringBuilder(), digit2LettersMap);
return combinations;
}
private List<String> combinations = new ArrayList<>();
private void combine(char[] digits, int index, StringBuilder sequence, Map<Character, List<String>> d2LMap) {
if (index >= digits.length) {
this.combinations.add(sequence.toString());
return;
}
for (int itr=0; itr<d2LMap.get(digits[index]).size(); ++itr) {
sequence.append(d2LMap.get(digits[index]).get(itr));
this.combine(digits, index+1, sequence, d2LMap);
sequence.deleteCharAt(sequence.length()-1);
}
}
}