营销网站怎么做,做电商引流软文网站,wordpress文章版权信息,微信小程序模板源码力扣#xff1a;17. 电话号码的字母组合
描述
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。
示例 1#xff1a;
输…力扣17. 电话号码的字母组合
描述
给定一个仅包含数字 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 4 digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
1.递归
排列组合的方式例如 题目中的“23”对应为“abc”“def”,按下2和3时能出现的选择只有“a”“b”c和“d”“e”“f”然而按下第一个数字2“a”“b”c不能互相排列再次按下数字3“d”“e”“f”可以和前面的“a”“b”c互相组合组合的可能就为[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 可按照下面设计代码 1.创建数组存储第一个数字对应的字母 2.将第二个数字对应的字母遍历一遍一一添加到数组中
#includeiostream
#includevector
using namespace std;
class Solution{
public:string m[10] {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring letterCombinations(string digits){vectorstring res;for(int i 0; i digits.size(); i){combine(res,digits[i]);}return res;}void combine(vectorstring res,char ch){int n res.size();int digit static_castint(ch)-48;int l m[digit].size();if(n 0){//第一个数字对应的字母添加到数组中for(auto j 0; j l; j){string s(1,m[digit][j]);res.push_back(s);}return;}for(int i 0; i n; i){//将第二个数字对应的字母遍历添加到数组中for(int j 0; j l - 1; j){res.push_back(res[i] m[digit][j]);}res[i] m[digit][l-1];}return;}
};int main(){Solution solution;string digits 79;vectorstring result solution.letterCombinations(digits);cout ALL possible combinations for digits digits are endl;for(const string str:result){cout str ;}cout endl;return 0;}2.队列
先将第一个数字对应的字符入队之后每次从队头取出一个元素与m[]中字符串中的未组合的字符分别组合然后放入队尾。
#includeiostream
#includequeue
#includevector
#includemap
using namespace std;
class Solution {
public:vectorstring letterCombinations(string digits) {mapchar, string m { {2, abc}, {3, def}, {4, ghi}, {5, jkl},{6, mno}, {7, pqrs}, {8, tuv}, {9, wxyz} };std::queuestring q;vectorstring res;// 先处理第一个数字。是为了使q不为空。for (auto i : m[digits[0]]) {string s(1, i);q.push(s);} //处理第二个及以后的数字for (auto i 1; i digits.size(); i) {int len q.size();for (auto j 0; j len; j) {string s q.front(); //队首的字符for (auto k 0; k m[digits[i]].size(); k) {q.push(s m[digits[i]][k]); //队首的字符和余下对应号码未组合的字符组合}q.pop(); //删除队首的字符}}while (!q.empty()) {res.push_back(q.front());q.pop();}return res;}
};int main()
{Solution solution;string digits 679;vectorstring result solution.letterCombinations(digits);cout All possibile combinations for digits digits are endl;for(const string str:result){cout str ;}cout endl;return 0;
} 3.搜索(深度优先)
3.1
对一个数字对应的字符都搜索排列完成后在进行第二个数字对应的字符搜索排列在进行第三个 和队列的思想类似
#includeiostream
#includevector
#includequeue
using namespace std;
class Solution{
public:vectorstring letterCombinations(string digits){vectorstringres;if(digits.empty()) return res;vectorstringletter({,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz});string path ;DFS(digits,0,path,res,letter);return res;}void DFS(string digits, int pos, string path, vectorstring res, vectorstring letter){if(pos digits.size()){res.push_back(path);return;}for(auto c:letter[digits[pos] - 0]){path.push_back(c);DFS(digits, pos 1, path, res, letter);path.pop_back();}}
};int main()
{Solution solution;string digits 679;vectorstring result solution.letterCombinations(digits);cout All possibile combinations for digits digits are endl;for(const string str:result){cout str ;}cout endl;return 0;
}3.2
每次递归调用时将新的字符直接添加到 path 的末尾而不是像之前那样在函数调用之间不断地对 path 进行 push_back 和 pop_back 操作。这种直接在递归调用中更新 path 的方式避免了频繁的操作简化了代码逻辑。
#includeiostream
#includevector
#includequeue
using namespace std;
class Solution {
public:vectorstring letterCombinations(string digits) {vectorstringres;if(digits.empty()) return res;vectorstringletter({, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz});string path ;DFS(digits, 0, path, res, letter);return res;}//此处修改string path,为传值方式void DFS(string digits, int pos, string path, vectorstring res, vectorstring letter){if(pos digits.size()){res.push_back(path);return;}for(auto c: letter[digits[pos] - 0]){DFS(digits, pos 1, path c, res, letter);}}
};int main()
{Solution solution;string digits 679;vectorstring result solution.letterCombinations(digits);cout All possibile combinations for digits digits are endl;for(const string str:result){cout str ;}cout endl;return 0;
}力扣官方给的解题方法为第三种
class Solution {
public:vectorstring letterCombinations(string digits) {vectorstring combinations;if (digits.empty()) {return combinations;}unordered_mapchar, string phoneMap{{2, abc},{3, def},{4, ghi},{5, jkl},{6, mno},{7, pqrs},{8, tuv},{9, wxyz}};string combination;backtrack(combinations, phoneMap, digits, 0, combination);return combinations;}void backtrack(vectorstring combinations, const unordered_mapchar, string phoneMap, const string digits, int index, string combination) {if (index digits.length()) {combinations.push_back(combination);} else {char digit digits[index];const string letters phoneMap.at(digit);for (const char letter: letters) {combination.push_back(letter);backtrack(combinations, phoneMap, digits, index 1, combination);combination.pop_back();}}}
};
力扣17. 电话号码的字母组合
