# [LeetCode] 017. Letter Combinations of a Phone Number (Medium) (C++/Java/Python)

Github:
https://github.com/illuz/leetcode

## 017.Letter_Combinations_of_a_Phone_Number (Medium)

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()) {
} 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

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！