题面
Given a string containing digits from 2-9
inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
(题面来自leetcode,包括图片)
我们知道电话按键每个数字都分别对应几个字母,现给定一串数字,找到所有可能的字符组合序列。
样例
Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
样例求解过程
思路
本题暴力遍历是不可取的,参考上图,可采用DFS深度优先遍历用递归来实现所有字母的组合。
Note: 要注意0和1的出现,没有字母与之对应,但需要考虑和处理。
DFS过程
1 dfs(para1, para2, ...) 2 { 3 if()//满足状态,返回 4 { 5 .... 6 return ; 7 } 8 //递归向下,继续搜索 9 for(....) 10 dfs(depth+1, ....) ; 11 12 return ; 13 }
源码
1 class Solution { 2 public: 3 vector<string> letterCombinations(string digits) { 4 int depth = digits.length(); 5 if(depth == 0) 6 return vector<string> {}; 7 8 string tmp(depth, 0); 9 vector<string> res; 10 dfs(tmp, 0, depth, res, digits); 11 return res; 12 } 13 //使用引用,提高效率 14 void dfs(string &tmp, int curdeep, int depth, vector<string> &ans, string &digits) 15 { 16 if(curdeep >= depth)//长度够了,就返回 17 { 18 ans.push_back(tmp); 19 return ; 20 } 21 for(int i = 0; i < dic[digits[curdeep]-'0'].length(); ++i) 22 { 23 tmp[curdeep] = dic[digits[curdeep]-'0'][i]; 24 dfs(tmp, curdeep+1, depth, ans, digits);//递归搜索 25 } 26 return ; 27 } 28 private: 29 string dic[10] = {{""}, {""}, {"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"}};//数字对应字符字典 30 };