文章目录

• 17. 电话号码的字母组合：
• • 样例 1：
  • 样例 2：
  • 样例 3：
  • 提示：
  • 原题传送门：
• 分析
• 题解
• • rust
  • go
  • c++
  • java
  • typescript
  • python

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 <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

原题传送门：

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 仔细看了看，好像没有什么特别的技巧。
• 递归套娃大法比较直观，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 {fn backtrack(ans: &mut Vec, digits: &[u8], index: usize, buf: &mut Vec) {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 []stringvar 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] = cbacktrack(index+1, buf)}}}if len(digits) > 0 {backtrack(0, make([]byte, len(digits)))}return ans
}

c++

class Solution {
private:unordered_map phoneMap{{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};void backtrack(vector &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 letterCombinations(string digits) {vector 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 letterCombinations(String digits) {List ans = new ArrayList<>();if (digits.length() > 0) {this.backtrack(ans, digits, 0, new char[digits.length()]);}return ans;}private void backtrack(List 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://le-yi.blog.csdn.net/ 博客原创~