LiaoyiLeetCode 17. 电话号码的字母组合 中等
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
javascript
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
javascript
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解题思路
采用回溯做法，对于当前选项，我们可以重复选择，所以 for 循环那里从 0 开始，对于字母组合我们做一个 map映射即可。
参考 xiao_ben_zhu 大佬的图解
javascript
var letterCombinations = function (digits) {
if (!digits.length) return [];
// 直接映射
const map = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
let res = [];
let dfs = (cur, start) => {
if (start >= digits.length) {
res.push(cur);
return;
}
// 取当前可选的字母组合
let str = map[digits[start]];
for (let i = 0; i < str.length; i++) {
dfs(cur + str[i], start + 1);
}
};
dfs("", 0);
return res;
};
cpp
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> res;
string cur;
dfs(digits, 0, cur, res);
return res;
}
void dfs(string& digits, int start, string& cur, vector<string>& res) {
if (start >= digits.size()) {
res.push_back(cur);
return;
}
string str = map[digits[start]];
for (int i = 0; i < str.size(); i++) {
cur.push_back(str[i]);
dfs(digits, start + 1, cur, res);
cur.pop_back();
}
}
private:
unordered_map<char, string> map = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
};
java
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) return new ArrayList<>();
List<String> res = new ArrayList<>();
dfs(digits, 0, new StringBuilder(), res);
return res;
}
private void dfs(String digits, int start, StringBuilder cur, List<String> res) {
if (start >= digits.length()) {
res.add(cur.toString());
return;
}
String str = map.get(digits.charAt(start));
for (int i = 0; i < str.length(); i++) {
cur.append(str.charAt(i));
dfs(digits, start + 1, cur, res);
cur.deleteCharAt(cur.length() - 1);
}
}
private Map<Character, String> map = new HashMap<Character, String>() {
{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}
};
}
python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
res = []
self.dfs(digits, 0, '', res)
return res
def dfs(self, digits, start, cur, res):
if start >= len(digits):
res.append(cur)
return
str = self.map[digits[start]]
for i in range(len(str)):
self.dfs(digits, start + 1, cur + str[i], res)
map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
解法 2
这个是没用回溯之前写的一份代码，简单来说就是利用了层次遍历的特性，反正每次取字母都是可以重复的，直接遍历即可，然后进队列。
javascript
var letterCombinations = function (digits) {
if (!digits.length) return [];
const map = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
let queue = [];
queue.push("");
for (let i = 0; i < digits.length; i++) {
let size = queue.length;
while (size--) {
let cur = queue.shift();
let str = map[digits[i]];
for (let j = 0; j < str.length; j++) {
queue.push(cur + str[j]);
}
}
}
return queue;
};
cpp
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> res;
queue<string> q;
q.push("");
for (int i = 0; i < digits.size(); i++) {
int size = q.size();
while (size--) {
string cur = q.front();
q.pop();
string str = map[digits[i]];
for (int j = 0; j < str.size(); j++) {
q.push(cur + str[j]);
}
}
}
while (!q.empty()) {
res.push_back(q.front());
q.pop();
}
return res;
}
private:
unordered_map<char, string> map = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
};
java
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) return new ArrayList<>();
List<String> res = new ArrayList<>();
Queue<String> q = new LinkedList<>();
q.offer("");
for (int i = 0; i < digits.length(); i++) {
int size = q.size();
while (size-- > 0) {
String cur = q.poll();
String str = map.get(digits.charAt(i));
for (int j = 0; j < str.length(); j++) {
q.offer(cur + str.charAt(j));
}
}
}
while (!q.isEmpty()) {
res.add(q.poll());
}
return res;
}
private Map<Character, String> map = new HashMap<Character, String>() {
{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}
};
}
python
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
res = []
q = collections.deque()
q.append('')
for i in range(len(digits)):
size = len(q)
while size:
cur = q.popleft()
str = self.map[digits[i]]
for j in range(len(str)):
q.append(cur + str[j])
size -= 1
while q:
res.append(q.popleft())
return res
map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
javascript
学如逆水行舟，不进则退