程序员人生 网站导航

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

栏目:php教程时间:2015-03-23 08:17:49

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


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐