leetcode小白刷题之旅----17. Letter Combinations of a Phone Number

仅供自己学习

题目：

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:

Input: digits = ""
Output: []
Example 3:

Input: digits = "2"
Output: ["a","b","c"]

思路：

因为不限制答案输出的顺序，可以把传入的digits化成一张图，数字下跟着它存的字母，当前数字的所有字母又与当前数字的下一个数字相连。由此这个题就可以视为这个图能走多少条路，而这路径就由字母组合反映出来。并且采用DFS。

细节：

当我们探索一个数字后选择第一个字母然后再进入该函数重复执行，当搜索的深度即搜索的数字长度为digits的长度就把这串字符加入进用来存储结果的string里并返回。并用for循环重复执行函数使每一个数字里的每个字母都能探索，保证得到所有的图的路径。

代码

 1 class Solution {
 2 public:
 3     vector<string> letterCombinations(string digits) {
 4         if(digits.empty()) return{};
 5         vector<string> res;
 6         vector<string> dict{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 7         comeback(digits,dict,0,"",res);
 8         return res;
 9     }
10     void comeback(string digits,vector<string>& dig,int len,string out,vector<string>& res){
11         if(digits.size()==len) {res.push_back(out);return;}
12         string str = dig[digits[len]-‘0‘];
13         for(int i=0;i<str.size();++i){
14             comeback(digits,dig,len+1,out+str[i],res);
15         }
16     }
17     
18 };

leetcode小白刷题之旅----17. Letter Combinations of a Phone Number

原文：https://www.cnblogs.com/Mrsdwang/p/14337642.html