问题描述
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
解决思路
- use hashMap to store numbers and corresponding charaters
- recursive to add charaters into the String curr
- while curIdx reach to the length of digits, which means current recursive has been to the leaf, then add it into the res
- if it hasnt reach to the length of digits, get chars by use key curIdx and traverse all chars in it.
- recursive to add them
代码
class Solution {
public List<String> letterCombinations(String digits) {
//1. use hashMap to store numbers and corresponding charaters
//2. recursive to add charaters into the String curr
//3. while curIdx reach to the length of digits, which means
//current recursive has been to the leaf, then add it into the res
//4. if it hasnt reach to the length of digits, get chars by use key curIdx
//and traverse all chars in it.
//5. recursive to add them
List<String> res = new ArrayList<String>();
//corner case
if(digits.length() == 0 || digits == null) return res;
HashMap<Character, char[]> map = new HashMap<>();
map.put('2', new char[]{'a', 'b', 'c'});
map.put('3', new char[]{'d', 'e', 'f'});
map.put('4', new char[]{'g', 'h', 'i'});
map.put('5', new char[]{'j', 'k', 'l'});
map.put('6', new char[]{'m', 'n', 'o'});
map.put('7', new char[]{'p', 'q', 'r', 's'});
map.put('8', new char[]{'t', 'u', 'v'});
map.put('9', new char[]{'w', 'x', 'y', 'z'});
addCharacter("", 0, digits, res, map);
return res;
}
public void addCharacter(String curr, int currIdx, String digits, List<String> res, HashMap<Character, char[]> map){
//the curIdx reach to the length of digits
if(currIdx == digits.length()){
//add curr into res
res.add(curr);
}else{
//get the number in digits
char c = digits.charAt(currIdx);
//check whether the numer is 2-9 or not
if(map.containsKey(c)){
//get corresponding charater of the number
for(char ch: map.get(c)){
addCharacter(curr + ch, currIdx + 1, digits, res, map);
}
}
}
}
}
效率探究
时间效率：O(n)
空间效率：O(n^2)
