【LeetCode每日一题】——17.电话号码的字母组合
文章目录
- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【题目提示】
- 七【解题思路】
- 八【时间频度】
- 九【代码实现】
- 十【提交结果】
一【题目类别】
- 回溯
二【题目难度】
- 中等
三【题目编号】
- 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']
的一个数字。
七【解题思路】
- 但凡涉及到组合类的题目,基本都使用回溯算法解决,本题也不例外,不过是在原本的基础上添加映射关系
- 根据题目信息可知,我们最终组合的是字母,但是输入数据为数字,所以需要简历一个数字到字母的映射
- 其余步骤和正常的回溯过程一致
- 设置边界条件:如果所有的数字都遍历完毕了,就完成此次计算
- 回溯拼接某一电话号码对应的字母:和正常的回溯过程一致,不过需要先取出数字对应的字母进行回溯
- 最后返回结果即可
- 具体细节可以参考下面的代码
八【时间频度】
- 时间复杂度: O ( 3 m × 4 n ) O(3^m × 4^n) O(3m×4n), m m m为 3 3 3个字母对应的数字个数, n n n为 4 4 4个字母对应的数字个数
- 空间复杂度: O ( m + n ) O(m + n) O(m+n), m m m为 3 3 3个字母对应的数字个数, n n n为 4 4 4个字母对应的数字个数
九【代码实现】
- Java语言版
class Solution {
// 数字和字母的映射
private static final String[] phoneMap = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
public List<String> letterCombinations(String digits) {
// 边界条件的判断
if (digits == null || digits.length() == 0) {
return new ArrayList<>();
}
// 存储最终结果
List<String> res = new ArrayList<>();
// 从第一个电话号码开始计算
dfs(res, new StringBuffer(), digits, 0);
// 返回最终结算结果
return res;
}
// 使用回溯计算电话号码的字母组合
private void dfs(List<String> res, StringBuffer temp, String digits, int index) {
// 将所有电话号码遍历完毕即可返回
if (index == digits.length()) {
res.add(temp.toString());
return;
}
// 回溯拼接某一电话号码对应的字母
char digit = digits.charAt(index);
String letters = phoneMap[digit - '0'];
for (int i = 0; i < letters.length(); i++) {
temp.append(letters.charAt(i));
dfs(res, temp, digits, index + 1);
temp.deleteCharAt(temp.length() - 1);
}
}
}
- Python语言版
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 边界条件的判断
if not digits:
return list()
# 数字和字母的映射
phoneMap = {
"2" : "abc",
"3" : "def",
"4" : "ghi",
"5" : "jkl",
"6" : "mno",
"7" : "pqrs",
"8" : "tuv",
"9" : "wxyz",
}
# 存储最终结果
res = list()
# 存储临时结果
temp = list()
# 使用回溯计算电话号码的字母组合
def dfs(index):
# 将所有电话号码遍历完毕即可返回
if index == len(digits):
res.append("".join(temp))
return
# 回溯拼接某一电话号码对应的字母
digit = digits[index]
for letter in phoneMap[digit]:
temp.append(letter)
dfs(index + 1)
temp.pop()
# 从第一个电话号码开始计算
dfs(0)
# 返回最终结算结果
return res
- C++语言版
class Solution {
public:
// 数字和字母的映射
const vector<string> phoneMap = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
// 使用回溯计算电话号码的字母组合
void dfs(vector<string>& res, string& temp, string digits, int index) {
// 将所有电话号码遍历完毕即可返回
if (index == digits.size()) {
res.push_back(temp);
return;
}
// 回溯拼接某一电话号码对应的字母
int digit = digits[index] - '0';
const string& letters = phoneMap[digit];
for (char letter : letters) {
temp.push_back(letter);
dfs(res, temp, digits, index + 1);
temp.pop_back();
}
}
vector<string> letterCombinations(string digits) {
// 存储最终结果
vector<string> res;
// 边界条件的判断
if (digits.empty()) {
return res;
}
// 存储临时结果
string temp;
// 从第一个电话号码开始计算
dfs(res, temp, digits, 0);
// 返回最终结算结果
return res;
}
};
十【提交结果】
-
Java语言版
-
Python语言版
-
C++语言版