南京江宁网站制作公司,广西城乡住房建设厅网站首页,培训机构,网站开发需要会什么leetcode原题网页 题目描述#xff1a;给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。 思路#xff1a;使用vector#x…leetcode原题网页 题目描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 思路使用vector进行深度优先遍历
每个按键所对应的字母都是固定的。可以先创建一个数字到字母的映射数组。
vectorstringNumStrArr {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};
对于每一个可能得到的输入数字序列由于每一个数字可能对应多个字母当多个数字组合输入时则会出现树形组合方式如下图 采用深度优先遍历的方法即每次操作遍历完树的层数。结束一次遍历以后进行回溯回溯到上一层再取上一层的下一个字母往下递归直至上一层字母全部取完。
其实就是不断寻找所有可行解的过程但是对于本题来说每个字母组合都是可行的解。
class Solution {vectorstringNumStrArr {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};
public:void Combine(const string digits,int i,const string combinestr, vectorstring v){//i为目前所操作的数字在dights中的下标if(i digits.size()) //遍历层数已达最大已找到一个序列组合执行插入和回退操作{v.push_back(combinestr);return;}int ndigits[i]-0;string strNumStrArr[n];for(auto ch:str) //对于当前层数字所对应的string进行遍历{Combine(digits, i1, combinestrch, v);}}vectorstring letterCombinations(const string digits) {vectorstring v;if(digits.empty()) //如果digits为空表示没有输入直接返回return v;string str; //str用于维护可能的的字母组合Combine(digits, 0, str, v);return v;}
};
