给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
采用DFS
Map<Character, String> cache = new HashMap<>();
public List<String> letterCombinations(String digits) {
if(null == digits || digits.length() == 0) {
return new ArrayList<>();
}
cache.put('2', "abc");
cache.put('3', "def");
cache.put('4', "ghi");
cache.put('5', "jkl");
cache.put('6', "mno");
cache.put('7', "pqrs");
cache.put('8', "tuv");
cache.put('9', "wxyz");
List<String> res = new ArrayList<>();
createRes(0, new StringBuilder(), res, digits);
return res;
}
public void createRes(int index, StringBuilder s, List<String> res, String digits) {
if (index == digits.length()) {
res.add(s.toString());
return;
}
String curStr = cache.get(digits.charAt(index));
for(int i = 0;i < curStr.length();i++) {
createRes(index + 1, s.append(curStr.charAt(i)), res, digits);
s.deleteCharAt(s.length()-1);
}
return;
}
