# My very clear DFS solution from USC

• public class Solution {
public List<String> letterCombinations(String digits) {

``````    List<String> list = new ArrayList<String>();
if (digits == null || digits.length() == 0) {
return list;
}

Map<Integer, String> map = new HashMap<Integer, String>();
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");
map.put(0, "");
dfs(list, digits, 0, "", map);
return list;
}

private void dfs(List<String> list, String digits, int index, String str, Map<Integer, String> map) {

String temp_str = str;
if (temp_str.length() == digits.length()) {
//System.println(temp_str);
list.add(temp_str);
return;
}

Integer j = Character.getNumericValue(digits.charAt(index));
String map_str = map.get(j);
//System.out.println(map_str);
for (int i = 0; i < map_str.length(); i++) {
temp_str = temp_str + Character.toString(map_str.charAt(i));
dfs(list, digits, index + 1, temp_str, map);
temp_str = temp_str.substring(0, temp_str.length() - 1);
}
}
``````

}

• @zongtb you are master, I want to birth a monkey to you

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.