One minute
Leetcode 17
Letter Combination of a Phone Number
Head on over here to try the problem for yourself.
Most permutation based problems seem to use a back-tracking solution, but don’t quote me on that 😅
Algorithm
The goal is to get all permutations of letters corresponding to a given phone number. First, we create a mapping of numbers and the corresponding letters. Then we simply set up a backtracking function helper()
which will populate our result
list with the required solutions.
Code
public List<String> letterCombinations(String digit) {
List<String> result = new ArrayList();
if(digits.length() == 0) return result;
char[][] map = {
{'a','b','c'},
{'d','e','f'},
{'g','h','i'},
{'j','k','l'},
{'m','n','o'},
{'p','q','r','s'},
{'t','u','v'},
{'w','x','y','z'}
};
StringBuilder curr = new StringBuilder();
helper(result, curr, digits, map, 0);
return result;
}
public void helper(List<String> result, StringBuilder curr, String digits, char[][] map, int index) {
if(index >= digits.length()) {
result.add(curr.toString());
return;
}
for(char c : map[digits.charAt(i++) -'2']) {
helper(result, curr.append(c), digits, map, i);
curr.deleteCharAt(curr.length() - 1);
// deleteCharAt() here makes the solution
// move forward correctly in the for loop
}
}