Medium
這題用DFS,注意下每次搜索遍歷的下一個字符是digits.charAt(sb.length().然后要backtracking.
class Solution {
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0){
return res;
}
Map<Integer, List<Character>> map = new HashMap<>();
map.put(2, new ArrayList<Character>(Arrays.asList('a','b','c')));
map.put(3, new ArrayList<Character>(Arrays.asList('d','e','f')));
map.put(4, new ArrayList<Character>(Arrays.asList('g','h','i')));
map.put(5, new ArrayList<Character>(Arrays.asList('j','k','l')));
map.put(6, new ArrayList<Character>(Arrays.asList('m','n','o')));
map.put(7, new ArrayList<Character>(Arrays.asList('p','q','r','s')));
map.put(8, new ArrayList<Character>(Arrays.asList('t','u','v')));
map.put(9, new ArrayList<Character>(Arrays.asList('w','x','y','z')));
StringBuilder sb = new StringBuilder();
dfsHelper(res, map, sb, digits);
return res;
}
private void dfsHelper(List<String> res, Map<Integer, List<Character>> map, StringBuilder sb, String digits){
if (sb.length() == digits.length()){
res.add(sb.toString());
return;
}
for (char c : map.get(Character.getNumericValue(digits.charAt(sb.length())))){
sb.append(c);
dfsHelper(res, map, sb, digits);
sb.deleteCharAt(sb.length() - 1);
}
}
}
