There are 2 solutions the first one is wrong, the second one is right. Be careful!
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> r = new ArrayList<String>();
if (digits.length() == 0 || digits == null) return r;
String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
helper(digits, r, table, new StringBuilder(), 0, digits.length());
return r;
}
public void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {
if (pos >= n) {
String s = temp.toString();
r.add(s);
return;
}
for (int i=pos; i<n; i++) {
int curr = digits.charAt(i)-'0';
if (curr == 0 || curr == 1 || digits.charAt(i) == '*' || digits.charAt(i) == '#')
helper(digits, r, table, temp, i+1, n);
else {
String choice = table[curr];
for (int j=0; j<choice.length(); j++) {
char choiceCurr = choice.charAt(j);
temp.append(choiceCurr);
helper(digits, r, table, temp, i+1, n);
temp = new StringBuilder(temp.substring(0, temp.length()-1));
}
}
}
}
}
public class Solution {
public static List<String> letterCombinations(String digits) {
List<String> r = new ArrayList<String>();
if (digits == null) return r;
String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
if (digits.isEmpty()) {
r.add("");
return r;
}
helper(digits, r, table, new StringBuilder(), 0, digits.length());
return r;
}
public static void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {
if (pos >= n) {
String s = temp.toString();
r.add(s);
return;
}
int curr = digits.charAt(pos)-'0';
if (curr == 0 || curr == 1 || digits.charAt(pos) == '*' || digits.charAt(pos) == '#')
helper(digits, r, table, temp, pos+1, n);
else {
String choice = table[curr];
for (int j=0; j<choice.length(); j++) {
char choiceCurr = choice.charAt(j);
temp.append(choiceCurr);
helper(digits, r, table, temp, pos+1, n);
temp.deleteCharAt(pos);
}
}
}
}
No comments:
Post a Comment