---

---

17. 电商商城定制开发电话号码的字母组合：

电商商城定制开发给定一个仅包含数字 2-9 的，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

样例 1：

输入：	digits = "23"	输出：	["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2
3
4
5

样例 2：

输入：	digits = ""	输出：	[]
1
2
3
4
5

样例 3：

输入：	digits = "2"	输出：	["a","b","c"]
1
2
3
4
5

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

原题传送门：

---

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 仔细看了看，好像没有什么特别的技巧。
• 递归套娃大法比较直观，dfs，回溯。
• 细节的地方在于字符串拼接，有些语言的字符串是不可变的，在字符串拼接上有可以优化的点。

---

题解

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    }}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

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}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

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;    }};
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

---

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);            }        }    }}
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

---

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;};
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

---

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
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

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 博客原创~

---