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.
Although the above answer is in lexicographical order, your answer could be in any order you want.
Solution 1: Use dfs, use StringBuilder and char array could save some time. Pay attention, blank string "" should not be added to result.
public class Solution {
String[] dict={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
char[] dig=digits.toCharArray();
List<String> res=new ArrayList<>();
StringBuilder one=new StringBuilder();
dfs(dig,0,one,res);
return res;
}
private void dfs(char[] dig, int d, StringBuilder one, List<String> res) {
if (d==dig.length) {
if (d>0) res.add(one.toString()); //blank String "" should not be added
}
else {
int index=dig[d]-'0';
for (int i=0; i<dict[index].length(); i++) {
char c=dict[index].charAt(i);
one.append(c);
dfs(dig,d+1,one,res);
one.deleteCharAt(one.length()-1);
}
}
}
}
没有评论:
发表评论