题目描述
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
解题思路
这个题目显然直接枚举就可以,那么我们现在考虑的是如何进行枚举。
我们先枚举一下:
我们要的是ad,ae…。
这不就相当于中序遍历嘛。
那么我们就可以用递归的方式来求这个字符串了。
注意全局变量,参数,函数返回值的设计。
代码
class Solution { unordered_map<char,string> hash={ {'2',"abc"}, {'3',"def"}, {'4',"ghi"}, {'5',"jkl"}, {'6',"mno"}, {'7',"pqrs"}, {'8',"tuv"}, {'9',"wxyz"} }; vector<string> ret; public: vector<string> letterCombinations(string digits) { if(digits.size()==0) return {}; dfs(digits,0,""); return ret; } void dfs(string& digits,int pos,string s) { if(pos>=digits.size()) { ret.push_back(s); return ; } for(auto ch:hash[digits[pos]]) { dfs(digits,pos+1,s+ch); } } };