题目大意：给你一串电话号码，输出可以由这串电话号码打出的所有字符串。
Problem:
Given a digit string, 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.
|
1 2 |
Input:Digit string "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: DFS
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// Author: Huahua // Runtime: 0 ms class Solution { public: vector<string> letterCombinations(string digits) { if (digits.empty()) return {}; vector<vector<char>> d(10); d[0] = {' '}; d[1] = {}; d[2] = {'a','b','c'}; d[3] = {'d','e','f'}; d[4] = {'g','h','i'}; d[5] = {'j','k','l'}; d[6] = {'m','n','o'}; d[7] = {'p','q','r','s'}; d[8] = {'t','u','v'}; d[9] = {'w','x','y','z'}; string cur; vector<string> ans; dfs(digits, d, 0, cur, ans); return ans; } private: void dfs(const string& digits, const vector<vector<char>>& d, int l, string& cur, vector<string>& ans) { if (l == digits.length()) { ans.push_back(cur); return; } for (const char c : d[digits[l] - '0']) { cur.push_back(c); dfs(digits, d, l + 1, cur, ans); cur.pop_back(); } } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua // Running time: 3 ms class Solution { public List<String> letterCombinations(String digits) { String[] d = new String[]{" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; char[] cur = new char[digits.length()]; List<String> ans = new ArrayList<>(); dfs(digits, d, 0, cur, ans); return ans; } private void dfs(String digits, String[] d, int l, char[] cur, List<String> ans) { if (l == digits.length()) { if (l > 0) ans.add(new String(cur)); return; } String s = d[Character.getNumericValue(digits.charAt(l))]; for (int i = 0; i < s.length(); ++i) { cur[l] = s.charAt(i); dfs(digits, d, l + 1, cur, ans); } } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
""" Author: Huahua Running time: 60 ms """ class Solution: def letterCombinations(self, digits): def dfs(digits, d, l, cur, ans): if l == len(digits): if l > 0: ans.append("".join(cur)) return for c in d[ord(digits[l]) - ord('0')]: cur[l] = c dfs(digits, d, l + 1, cur, ans) d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"] cur = [' ' for _ in range(len(digits))] ans = [] dfs(digits, d, 0, cur, ans) return ans |
Solution 2: BFS
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Runtime: 3 ms class Solution { public: vector<string> letterCombinations(string digits) { if (digits.empty()) return {}; vector<vector<char>> d(10); d[0] = {' '}; d[1] = {}; d[2] = {'a','b','c'}; d[3] = {'d','e','f'}; d[4] = {'g','h','i'}; d[5] = {'j','k','l'}; d[6] = {'m','n','o'}; d[7] = {'p','q','r','s'}; d[8] = {'t','u','v'}; d[9] = {'w','x','y','z'}; vector<string> ans{""}; for (char digit : digits) { vector<string> tmp; for (const string& s : ans) for (char c : d[digit - '0']) tmp.push_back(s + c); ans.swap(tmp); } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua // Running time: 4 ms class Solution { public List<String> letterCombinations(String digits) { if (digits.length() == 0) return new ArrayList<String>(); String[] d = new String[]{" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; List<String> ans = new ArrayList<>(); ans.add(""); for (char digit : digits.toCharArray()) { List<String> tmp = new ArrayList<>(); for (String t : ans) { String s = d[Character.getNumericValue(digit)]; for (int i = 0; i < s.length(); ++i) tmp.add(t + s.charAt(i)); } ans = tmp; } return ans; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 61 ms """ class Solution: def letterCombinations(self, digits): if not digits: return [] d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"] ans = [""] for digit in digits: tmp = [] for s in ans: for c in d[ord(digit) - ord('0')]: tmp.append(s + c) ans = tmp return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment