17 Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
使用递归实现
class Solution {
public List<String> letterCombinations(String digits) {
List<String> ret=new ArrayList<>();
if(digits==null || digits.length()==0){
return ret;
}
char[][] map=new char[10][];
map[2]=new char[]{'a','b','c'};
map[3]=new char[]{'d','e','f'};
map[4]=new char[]{'g','h','i'};
map[5]=new char[]{'j','k','l'};
map[6]=new char[]{'m','n','o'};
map[7]=new char[]{'p','q','r','s'};
map[8]=new char[]{'t','u','v'};
map[9]=new char[]{'w','x','y','z'};
char[] arr=new char[digits.length()];
recur(digits,0,map,ret,arr);
return ret;
}
private void recur(String digits, int index, char[][] map,
List<String> ret, char[] arr){
if(index==arr.length){
ret.add(String.valueOf(arr));
return;
}
char cur=digits.charAt(index);
for(char c:map[cur-'0']){
arr[index]=c;
recur(digits, index+1, map, ret, arr);
}
}
}
class Solution {
public List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<>();
if(digits==null || "".equals(digits)) return list;
char[] arr=new char[digits.length()];
letter(digits,0,arr,list);
return list;
}
private void letter(String digits, int index, char[] arr, List<String> list){
if(index==arr.length) {
list.add(String.valueOf(arr));
return ;
}
char c=digits.charAt(index);
if('2'==c){
arr[index]='a';
letter(digits, index+1, arr, list);
arr[index]='b';
letter(digits, index+1, arr, list);
arr[index]='c';
letter(digits, index+1, arr, list);
} else if ('3'==c){
arr[index]='d';
letter(digits, index+1, arr, list);
arr[index]='e';
letter(digits, index+1, arr, list);
arr[index]='f';
letter(digits, index+1, arr, list);
} else if ('4'==c){
arr[index]='g';
letter(digits, index+1, arr, list);
arr[index]='h';
letter(digits, index+1, arr, list);
arr[index]='i';
letter(digits, index+1, arr, list);
} else if ('5'==c){
arr[index]='j';
letter(digits, index+1, arr, list);
arr[index]='k';
letter(digits, index+1, arr, list);
arr[index]='l';
letter(digits, index+1, arr, list);
} else if ('6'==c){
arr[index]='m';
letter(digits, index+1, arr, list);
arr[index]='n';
letter(digits, index+1, arr, list);
arr[index]='o';
letter(digits, index+1, arr, list);
} else if ('7'==c){
arr[index]='p';
letter(digits, index+1, arr, list);
arr[index]='q';
letter(digits, index+1, arr, list);
arr[index]='r';
letter(digits, index+1, arr, list);
arr[index]='s';
letter(digits, index+1, arr, list);
} else if ('8'==c){
arr[index]='t';
letter(digits, index+1, arr, list);
arr[index]='u';
letter(digits, index+1, arr, list);
arr[index]='v';
letter(digits, index+1, arr, list);
} else if ('9'==c){
arr[index]='w';
letter(digits, index+1, arr, list);
arr[index]='x';
letter(digits, index+1, arr, list);
arr[index]='y';
letter(digits, index+1, arr, list);
arr[index]='z';
letter(digits, index+1, arr, list);
}
}
}