17. Letter Combinations of a Phone Number - jiejackyzhang/leetcode-note GitHub Wiki
Given a digit string, 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.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
String类题目。典型的recursion problem。
If the current digit is past the last digit
Add the letters to result list
Else
For each of the letters that can represent the current digit
Have the letter represent the current digit
Move to next digit and recurse
public class Solution {
private Map<Character, String> mapping = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<String>();
if(digits == null || digits.length() == 0 || digits.contains("0") || digits.contains("1")) {
return res;
}
letterCombinationsHelper(digits, "", res);
return res;
}
private void letterCombinationsHelper(String digits, String letters, List<String> res) {
if(letters.length() == digits.length()) {
res.add(letters);
return;
}
for(char c : mapping.get(digits.charAt(letters.length())).toCharArray()) {
letterCombinationsHelper(digits, letters+c, res);
}
}
}