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

索引:[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

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

波比源码 » [LeetCode] 017. Letter Combinations of a Phone Number (Medium) (C++/Java/Python)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡