17. 电话号码的字母组合：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
样例 1：
输入：
digits = "23"
输出：
["ad","ae","af","bd","be","bf","cd","ce","cf"]
样例 2：
输入：
digits = ""
输出：
[]
样例 3：
输入：
digits = "2"
输出：
["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 仔细看了看，好像没有什么特别的技巧。
- 递归套娃大法比较直观，dfs，回溯。
- 细节的地方在于字符串拼接，有些语言的字符串是不可变的，在字符串拼接上有可以优化的点。
题解
rust
const PHONE_MAP: &[&[char]] = &[&[], &[], &['a', 'b', 'c'], &['d', 'e', 'f'], &['g', 'h', 'i'], &['j', 'k', 'l'], &['m', 'n', 'o'], &['p', 'q', 'r', 's'], &['t', 'u', 'v'], &['w', 'x', 'y', 'z']];
impl Solution {
pub fn letter_combinations(digits: String) -> Vec<String> {
fn backtrack(ans: &mut Vec<String>, digits: &[u8], index: usize, buf: &mut Vec<u8>) {
if index == digits.len() {
ans.push(String::from_utf8(buf.clone()).unwrap());
} else {
let digit = (digits[index] - '0' as u8) as usize;
PHONE_MAP[digit].iter().for_each(|c| {
buf[index] = *c as u8;
backtrack(ans, digits, index + 1, buf);
});
}
}
let mut ans = Vec::new();
if digits.len() > 0 {
backtrack(&mut ans, digits.as_bytes(), 0, &mut vec![0; digits.len()]);
}
ans
}
}
go
var phoneMap [][]byte = [][]byte{
{
}, {
}, {
'a', 'b', 'c'}, {
'd', 'e', 'f'}, {
'g', 'h', 'i'}, {
'j', 'k', 'l'}, {
'm', 'n', 'o'}, {
'p', 'q', 'r', 's'}, {
't', 'u', 'v'}, {
'w', 'x', 'y', 'z'}}
func letterCombinations(digits string) []string {
var ans []string
var backtrack func(int, []byte)
backtrack = func(index int, buf []byte) {
if index == len(digits) {
ans = append(ans, string(buf))
} else {
digit := digits[index]
for _, c := range phoneMap[digit-'0'] {
buf[index] = c
backtrack(index+1, buf)
}
}
}
if len(digits) > 0 {
backtrack(0, make([]byte, len(digits)))
}
return ans
}
c++
class Solution {
private:
unordered_map<char, string> phoneMap{
{
'2', "abc"},
{
'3', "def"},
{
'4', "ghi"},
{
'5', "jkl"},
{
'6', "mno"},
{
'7', "pqrs"},
{
'8', "tuv"},
{
'9', "wxyz"}
};
void backtrack(vector<string> &ans, const string &digits, int index, string &buf) {
if (index == digits.length()) {
ans.emplace_back(buf);
} else {
char digit = digits[index];
for (const char &c: phoneMap.at(digit)) {
buf.push_back(c);
backtrack(ans, digits, index + 1, buf);
buf.pop_back();
}
}
}
public:
vector<string> letterCombinations(string digits) {
vector<string> ans;
if (digits.size() > 0) {
string buf;
backtrack(ans, digits, 0, buf);
}
return ans;
}
};
java
class Solution {
private static final char[][] PHONE_MAP = new char[][]{
{
},{
},{
'a','b','c'},{
'd','e','f'},{
'g','h','i'},{
'j','k','l'},{
'm','n','o'},{
'p','q','r','s'},{
't','u','v'},{
'w','x','y','z'}};
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits.length() > 0) {
this.backtrack(ans, digits, 0, new char[digits.length()]);
}
return ans;
}
private void backtrack(List<String> ans, String digits, int index, char[] buf) {
if (index == digits.length()) {
ans.add(new String(buf));
} else {
int digit = digits.charAt(index) - '0';
for (char c : PHONE_MAP[digit]) {
buf[index] = c;
backtrack(ans, digits, index + 1, buf);
}
}
}
}
typescript
const phoneMap = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz',
};
function letterCombinations(digits: string): string[] {
let ans = [];
const backtrack = function (index: number, buf: string) {
if (index == digits.length) {
ans.push(buf);
} else {
const digit = digits[index];
for (const c of phoneMap[digit]) {
backtrack(index + 1, buf + c);
}
}
};
if (digits.length > 0) {
backtrack(0, "");
}
return ans;
};
python
class Solution:
PHONE_MAP = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}
def letterCombinations(self, digits: str) -> List[str]:
def backtrack(index: int):
if index == len(digits):
ans.append("".join(buf))
else:
digit = digits[index]
for letter in Solution.PHONE_MAP[digit]:
buf.append(letter)
backtrack(index + 1)
buf.pop()
ans = list()
buf = list()
if len(digits) > 0:
backtrack(0)
return ans
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
