#leetcode刷题之路17-电话号码的字母组合
2019-03-13 23:29:14来源:博客园 阅读 ()
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
先看下图解释:
这道题肯定用的是递归。
首先我们可以看到,输入了几个数字,最终答案里的每一个小项的长度就是几。(例如:我们输入了2 3,这是两个数字,那么答案中的ad、ae、等都是由两个字符组成)
接着,我们那图中列举的第一种情况来分析,首先在第一层我们取首数字的第一个字母元素a,第一层就是在遍历首数字对应的字母,在第二层我们遍历第二个数字对应的字母。要注意这里遍历结束的条件:第一层结束的条件是首数字对应的字母遍历完了,第二层结束条件是第二个字母遍历完了,而当已经生成了由两个字母组成的字符串时,就把这个串加入最终的结果队列。
由此看见,输入的数字的个数、遍历到数字对应的第几个字母、当前生成的字符串(长度),这些都是影响递归的因素。同时,变量中还应有存放答案项的vector以及存放数字字母对应关系的map。
#include <iostream> #include <map> #include <vector> using namespace std; void combine(string digits,int seq,string current,vector<string> &ans,map<char ,string>num_letters) { if(digits.size()==seq) ans.push_back(current); else { for(int i=0;i<num_letters[digits[seq]].size();i++)//每一层的遍历 { combine(digits,seq+1,current+num_letters[digits[seq]][i],ans,num_letters); } } } vector<string> letterCombinations(string digits) { vector<string> ans; map<char,string> num_letters; if(digits=="") return ans; num_letters['2']="abc"; num_letters['3']="def"; num_letters['4']="ghi"; num_letters['5']="jkl"; num_letters['6']="mno"; num_letters['7']="pqrs"; num_letters['8']="tuv"; num_letters['9']="wxyz"; combine(digits,0,"",ans,num_letters); return ans; } int main() { string digits="23"; vector<string> ans=letterCombinations(digits); cout<<ans.size()<<endl; return 0; }
原文链接:https://www.cnblogs.com/biat/p/10517841.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- OI之路 2019-10-25
- 小白的C++之路——求质数 2019-10-25
- #leetcode刷题之路19-删除链表的倒数第N个节点 2019-03-13
- #leetcode刷题之路16-最接近的三数之和 2019-03-12
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash