LeetCode(17):电话号码的字母组合
2024-10-11 08:32:29
Medium!
题目描述:
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
解题思路:
这道题让我们求电话号码的字母组合,即数字2到9中每个数字可以代表若干个字母,然后给一串数字,求出所有可能的组合。
我们用递归Recursion来解,要建立一个字典,用来保存每个数字所代表的字符串,然后还需要一个变量level,记录当前生成的字符串的字符个数。
C++参考答案一:
// Recursion
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) return res;
string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//建立一个字典,用来保存每个数字所代表的字符串
letterCombinationsDFS(digits, dict, , "", res);
return res;
}
void letterCombinationsDFS(string digits, string dict[], int level, string out, vector<string> &res) {
if (level == digits.size()) res.push_back(out);
else {
string str = dict[digits[level] - ''];
for (int i = ; i < str.size(); ++i) {
out.push_back(str[i]);
letterCombinationsDFS(digits, dict, level + , out, res);
out.pop_back();
}
}
}
};
这道题我们也可以用迭代Iterative来解.
C++参考答案二:
// Iterative
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) return res;
string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
res.push_back("");
for (int i = ; i < digits.size(); ++i) {
int n = res.size();
string str = dict[digits[i] - ''];
for (int j = ; j < n; ++j) {
string tmp = res.front();
res.erase(res.begin());
for (int k = ; k < str.size(); ++k) {
res.push_back(tmp + str[k]);
}
}
}
return res;
}
};
最新文章
- NOPI Excel插件导入导出 图片批注
- Error occurred during initialization of VM java/lang/NoClassDefFoundError: java/lang/Object
- ExtJS学习之路第五步:认识最常见组件Panel
- 删除提示 FOREIGN KEY 约束引用”
- 致诸位新程序员:来自Chuck Jazdzewski慈父般的忠告
- JAVA的StringBuffer类
- SharePoint 2010 master page 控件介绍(2):ribbon (一同事读听着像泪奔)
- angular中的$http配置和参数
- Bootstrap 按钮分组
- LoadRunner接口工作总结
- iOS中 iOS10 权限崩溃问题 韩俊强的CSDN博客
- 工作流JBPM
- table-cell width:1% 深入理解
- 为什么CentOS7中找不到mysql服务,并且还找不到mysql.sock?
- Web开发——HTML基础(图像、音频和视频内容)
- ML: 聚类算法R包-K中心点聚类
- Knockout学习,添加模板,事件,Mouseover,mouseout
- bzoj 4464 : [Jsoi2013]旅行时的困惑
- linux高精度struct timespec 和 struct timeval
- [深入理解Android卷一全文-第四章]深入理解zygote
热门文章
- [转帖]linux namespace 和cgroup lxc
- [转载] 什么是istio 官网内容
- 用友时空KSOA功能挖掘之zl_func函数
- Vue实现对数组、对象的深拷贝、复制
- JavaFile类和递归
- mininet invalid literal for int() with base 10: &#39;cpu.cfs_period_us:&#39;
- Session in BSU CodeForces - 1027F(思维 树 基环树 离散化)
- 【题解】 bzoj1088: [SCOI2005]扫雷Mine (神奇的做法)
- 【poj3693】 Maximum repetition substring
- debian9部署jenkins