索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github:
https://github.com/illuz/leetcode
017.Letter_Combinations_of_a_Phone_Number (Medium)
链接：
题目：https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/
代码(github)：https://github.com/illuz/leetcode
题意：
在手机上按字母，给出按的数字键，问所有的按的字母的情况。
分析：
DFS 过去是比较轻松的写法。
代码：
C++:
class Solution {
private:
const string alpha[10] = {
" ",
"1", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"
};
void dfs(vector<string> &res, string &ab, string &digits, int cur) {
if (cur >= digits.length()) {
res.push_back(ab);
return;
}
for (auto &a : alpha[digits[cur] - '0']) {
ab.push_back(a);
dfs(res, ab, digits, cur + 1);
ab.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
string alphas;
dfs(res, alphas, digits, 0);
return res;
}
};
Java:
public class Solution {
private String[] alpha = new String[] {
" ",
"1", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"
};
private StringBuilder word;
private void dfs(List<String> res, String digits, int cur) {
if (cur >= digits.length()) {
res.add(word.toString());
} else {
for (int i = 0; i < alpha[digits.charAt(cur) - '0'].length(); ++i) {
word.append(alpha[digits.charAt(cur) - '0'].charAt(i));
dfs(res, digits, cur + 1);
word.deleteCharAt(word.length() - 1);
}
}
}
public List<String> letterCombinations(String digits) {
List<String> ret = new ArrayList<String>();
word = new StringBuilder();
dfs(ret, digits, 0);
return ret;
}
}
Python:
class Solution:
# @return a list of strings, [s1, s2]
def letterCombinations(self, digits):
alpha = [" ", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = []
word = []
def dfs(cur):
if cur >= len(digits):
res.append(''.join(word))
else:
for x in alpha[(int)(digits[cur]) - (int)('0')]:
word.append(x)
dfs(cur + 1)
word.pop()
dfs(0)
return res