-
Notifications
You must be signed in to change notification settings - Fork 1
/
17-letter-combination-of-a-phone-number.java
38 lines (31 loc) · 1.29 KB
/
17-letter-combination-of-a-phone-number.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
* 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 digits 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"]
*/
class Solution {
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if(digits == null || digits.length() == 0) {
return ans;
}
String[] lettersMap = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
backtrack(ans, new StringBuilder(), digits, lettersMap, 0);
return ans;
}
public static void backtrack(List<String> res, StringBuilder sb, String digits, String[] lettersMap, int idx) {
if(idx == digits.length()) {
res.add(sb.toString());
return;
}
int number = digits.charAt(idx) - '0';
String numStr = lettersMap[number - 2];
for(int i = 0; i < numStr.length(); i++) {
sb.append(numStr.charAt(i));
backtrack(res, sb, digits, lettersMap, idx + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}