网站关于页面,免费手机网页制作,wordpress主题安装500,微信公众平台开发者工具1. 题目链接#xff1a;17. 电话号码的字母组合
2. 题目描述#xff1a; 给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。…1. 题目链接17. 电话号码的字母组合
2. 题目描述 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2 输入digits
输出[]示例 3 输入digits 2
输出[a,b,c]提示 0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。 3. 解法
3.1 算法思路
每个位置可以选择的字符与其他位置并不冲突因此不需要标记已经出现的字符只需要将每个数字依次填入字符串中进行递归在回溯是撤销填入操作即可
在递归之前我们需要定义一个的字典 hash纪录2~9各自对应的字符
3.2 递归函数流程
递归结束条件时当pos等于digits的长度时将path加入到ret中返回取出当前处理的数字digits根据 hash取出的对应的字母列表letters遍历字母列表letters将当前字母加入到组合字符串path的末尾然后递归处理下一个数字传入pos1表示处理下一个数字递归处理结束后将加入的字母从path的末尾删除表示回溯最终返回ret即可 3.3 C算法代码
class Solution {string hash[10]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz}; // 定义一个字符串数组存储每个数字对应的字母组合string path; // 定义一个字符串变量存储当前生成的字母组合vectorstring ret; // 定义一个字符串向量存储所有可能的字母组合结果
public:vectorstring letterCombinations(string digits) { // 定义一个公共成员函数接受一个字符串参数digits表示输入的数字序列if(digits.size()0) return ret; // 如果输入的数字序列为空则直接返回空的结果向量retdfs(digits,0); // 否则调用dfs函数进行深度优先搜索return ret; // 返回结果向量ret}void dfs(string digits,int pos) // 定义一个私有成员函数dfs接受两个参数一个是输入的数字序列digits另一个是当前处理的位置pos{if(posdigits.size()) // 如果当前位置等于数字序列的长度{ret.push_back(path); // 将当前的字母组合添加到结果向量ret中return; // 返回}for(auto ch:hash[digits[pos]-0]) // 遍历当前数字对应的字母组合{path.push_back(ch); // 将字母添加到path中dfs(digits,pos1); // 递归地调用dfs函数处理下一个位置的数字path.pop_back(); // 将最后一个添加的字母从path中移除}}
};
