题目
()
问题分析
刚拿到这道题的时候没什么思路, 只能顺着逻辑想. 每个数字对应着三个或者四个字母, 也就是说每个位置我们会有三个或者四个选择. 那么似乎我们可以用递归来解决问题, 因为每个位置的字母我们都需要做多种选择, 而做出这种选择后下一个位置同样也需要这么做. 那么我们先依据这个思路写一个递归函数
- /*
- C++ 代码
- */
- /*
- ret 为储存最终结果的数组
- map 是字母到数字的映射表
- digits 是一串要转换数字
- s 由数字转换成的字符串
- */
- void fun(vector<string>& ret, const char map[8][5], const string& digits, string& s) {
- if (s.length() <digits.length()) {
- for (int i = 0; i < strlen(map[(digits[s.length()] - '0') - 2]); i++) {
- s.push_back(map[(digits[s.length()] - '0') - 2][i]);
- fun(ret,map,digits,s);
- s.pop_back();
- }
- }
- else if (s.length() == digits.length()) {
- ret.push_back(s);
- }
- }
可能有朋友发现这就是一个深度优先搜索的过程, 那么恭喜, 后面的内容将十分容易理解, 如果没有反应过来, 后面还有图片助于理解.
这个函数的部分执行过程见下图 (其实是画图太麻烦懒得画全过程, 也没必要), 看了之后理解起来应该更容易.
由于最终我们要返回一个数组给 LeetCode, 外层套上一个函数
- /*
- C++ 代码
- */
- vector<string> letterCombinations(string digits) {
- vector<string> ret;
- if (digits.length() == 0) {
- return ret;
- }
- char map[8][5] = {
- {'a','b','c',0},
- {'d','e','f',0},
- {'g','h','i',0},
- {'j','k','l',0},
- {'m','n','o',0},
- {'p','q','r','s',0},
- {'t','u','v',0},
- {'w','x','y','z',0}
- };
- string s;
- fun(ret, map, digits, s);
- return ret;
- }
时间复杂度 O(4^n) , 空间复杂度 O(n).
来源: http://www.bubuko.com/infodetail-2814378.html