Description
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
Input: "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.
solution 1
一看題干悼瘾，很明顯是組合問(wèn)題眉菱。沒(méi)有想到很好的解決方法猜年，先暴力解決。
private static final char[][] map = {{},{'a','b','c'},{'d','e','f'}
,{'g','h','i'},{'j','k','l'},{'m','n','o'}
,{'p','q','r', 's'},{'t','u','v'},{'w','x','y', 'z'}};
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return new ArrayList<>();
}
List<List<String>> result = new ArrayList<>();
for (int i = 0; i < digits.length(); i++) {
if (result.size() == 0) {
List<String> list = new ArrayList<>();
for (char c : map[digits.charAt(i) - '1']) {
list.add(String.valueOf(c));
}
result.add(list);
} else {
List<String> list = new ArrayList<>();
for (char c : map[digits.charAt(i) - '1']) {
for (String s : result.get(i - 1)) {
list.add(new StringBuilder(s).append(c).toString());
}
}
result.add(list);
}
}
return result.get(digits.length() - 1);
}
粗略一看，復(fù)雜度大概是。
提交代碼:
leetcode提交結(jié)果
emmm，有點(diǎn)小意外诅炉。
