C++?電話號碼的字母組合功能實現(xiàn)
電話號碼的字母組合
描述
給定一個僅包含數(shù)字 2-9 的字符串,返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下(與電話按鍵相同)。注意 1 不對應(yīng)任何字母。
示例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']
的一個數(shù)字。
思路/解法
方式一
回溯算法,在當(dāng)前題目非常適合。先使用map容器記錄所有可能,在回溯遍歷即可。
class Solution { public: void TrackBack(string& digits,int charStart,int size,string& back,vector<string>& res,std::unordered_map<char,string>& maps) { if(back.length() == size) { res.push_back(back); return; } int length = maps[digits[charStart]].length(); std::string str = maps[digits[charStart]]; for(int i = 0;i < length; i++) { back.push_back(str[i]); TrackBack(digits,charStart + 1,size,back,res,maps); back.pop_back(); } } vector<string> letterCombinations(string digits) { vector<string> arrs; if(digits == "") return arrs; std::unordered_map<char,string> maps{{'2',"abc"},{'3',"def"},{'4',"ghi"}, {'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}}; string back; TrackBack(digits,0,digits.length(),back,arrs,maps); return arrs; } };
方式二
遞歸法,使用遞歸求解出所有的可能性并合并結(jié)果即可。
class Solution { public: vector<string> CharCombine(string digits,unordered_map<char,string>& maps) { vector<string> tmp; int length = digits.size(); //邊界條件(當(dāng)長度為0或1時直接跳出) if(1 == length) { string str = maps[digits[0]]; for(int j = 0;j < str.length();j++) { string s = ""; tmp.push_back(s.append(1,str[j])); } return tmp; } else if(0 == length) return tmp; else//遞歸 { string str = maps[digits[length-1]]; vector<string> res = CharCombine(digits.substr(0,length-1),maps); for(int i = 0;i < str.length();i++) { for(int j = 0;j < res.size();j++) { string t = res[j]; tmp.push_back(t.append(1,str[i])); } } return tmp; } } vector<string> letterCombinations(string digits) { std::unordered_map<char,string> maps{{'2',"abc"},{'3',"def"},{'4',"ghi"}, {'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}}; return CharCombine(digits,maps); } };
到此這篇關(guān)于C++ 電話號碼的字母組合的文章就介紹到這了,更多相關(guān)C++ 電話號碼的字母組合內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
c++中將二維數(shù)組元素變換為逆向存放的實現(xiàn)代碼
編程將一個二維數(shù)組元素變換為逆向存放,即按元素在內(nèi)存中的物理排列位置,第一個元素變成倒數(shù)第一個元素,第二個元素變成倒數(shù)第二個元素,依此類推2020-11-11C語言 不使用strcat函數(shù)實現(xiàn)連接兩個字符串功能代碼
今天小編就為大家分享一篇C語言 不使用strcat函數(shù)實現(xiàn)連接兩個字符串功能代碼,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12C語言用循環(huán)單鏈表實現(xiàn)約瑟夫環(huán)
這篇文章主要為大家詳細介紹了C語言用循環(huán)單鏈表實現(xiàn)約瑟夫環(huán),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-10-10詳解基于C++實現(xiàn)約瑟夫環(huán)問題的三種解法
約瑟夫環(huán)問題是算法中相當(dāng)經(jīng)典的一個問題,其問題理解是相當(dāng)容易的,并且問題描述有非常多的版本,并且約瑟夫環(huán)問題還有很多變形,通過這篇約瑟夫問題的講解,一定可以帶你理解透徹2021-06-06