"""
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.
"""
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return [];
DigitString = {
'0' : " ",
'1' : "*",
'2' : "abc",
'3' : "def",
'4' : "ghi",
'5' : "jkl",
'6' : "mno",
'7' : "pqrs",
'8' : "tuv",
'9' : "wxyz"
}
if digits in DigitString:
return list(DigitString[digits]);
else:
return [a+b for a in self.letterCombinations(digits[0])
for b in self.letterCombinations(digits[1:])]
public class Solution {
public List<String> letterCombinations(String digits) {
HashMap<Character, String> keys = new HashMap<Character,String>();
keys.put('2', "abc");
keys.put('3', "def");
keys.put('4', "ghi");
keys.put('5', "jkl");
keys.put('6', "mno");
keys.put('7', "pqrs");
keys.put('8', "tuv");
keys.put('9', "wxyz");
List<String> res = new ArrayList<String>();
StringBuilder temp = new StringBuilder();
if(digits == null || digits.length() == 0) return res;
boolean[] flag = {true}; //set to false when meet invalid char
backtracking(digits, keys, temp, res, 0, flag);
return res;
}
private void backtracking(String digits, HashMap<Character, String> keys, StringBuilder temp, List<String> res, int start, boolean[] flag) {
if(!flag[0]) return;
int len = digits.length();
if(start == len){
res.add(temp.toString());
return;
}
char num = digits.charAt(start);
if(keys.containsKey(num)) {
String candidates = keys.get(num);
for(int j = 0; j < candidates.length(); j++) {
temp.append(candidates.charAt(j));
backtracking(digits, keys, temp, res, start + 1, flag);
temp.setLength(temp.length() - 1);
}
} else {
flag[0] = false;
}
}
}
public class Solution {
String[] phoneButtons = new String[] {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0) return res;
helper(digits, 0, new StringBuilder(), res);
return res;
}
public void helper(String digits, int index, StringBuilder sb, List<String> results) {
if (index == digits.length()) {
results.add(sb.toString());
return;
}
int digit = digits.charAt(index) - '0';
char[] characters = phoneButtons[digit].toCharArray();
for (char c : characters) {
sb.append(c);
helper(digits, index+1, sb, results);
sb.deleteCharAt(sb.length()-1);
}
}
}