力扣題庫電話號碼的字母組合-創(chuàng)新互聯(lián)

寒假算法學(xué)習(xí)與練習(xí) 每日一題

電話轉(zhuǎn)字母

創(chuàng)新互聯(lián)公司專注于梅里斯企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,商城系統(tǒng)網(wǎng)站開發(fā)。梅里斯網(wǎng)站建設(shè)公司,為梅里斯等地區(qū)提供建站服務(wù)。全流程按需求定制開發(fā)，專業(yè)設(shè)計，全程項目跟蹤，創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

題目描述：給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按任意順序返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。力扣

對于這道題想到的第一步是使用鍵值對，將數(shù)字對應(yīng)到一個一個字符，想的是將字符都放在列表中，然后遍歷digit，把每一個數(shù)字對應(yīng)的列表列出來，然后來進(jìn)行排列組合，這樣的方法會使時間復(fù)雜度大大增大。作為菜雞的我，去看了看大佬的解題方法，實現(xiàn)使用鍵值對，這個想法是對的，就是后面的處理，想的太復(fù)雜了，該題使用回溯法，大大降低了時間復(fù)雜度。

學(xué)習(xí)一下回溯法的基本思想

回溯法基本思想：

就是列出所有情況，然后用深度優(yōu)先搜索解空間樹（就是列出所有結(jié)果），回溯就是回到父節(jié)點，去往另外一個子節(jié)點。這里就不過多贅述了。

該題回溯思想：

解空間樹：

代碼：

void backtrack(vector&result,const unordered_map&phonemap,const string &digits,int index,string&combination)
{
 ? ?if(index==digits.length())
 ?  {
 ? ? ? ?result.push_back(combination);
 ?  }
 ? ?else{
 ? ? ? ?char digit=digits[index];
 ? ? ? ?const string &letters=phonemap.at(digit);
 ? ? ? ?for(const char&letter:letters)
 ? ? ?  {
 ? ? ? ? ? ?combination.push_back(letter);//第一個字母
 ? ? ? ? ? ?backtrack(result,phonemap,digits,index+1,combination);//往下
 ? ? ? ? ? ?combination.pop_back();//下一個字母
 ? ? ?  }
 ?  }
}
vectorletterCombinations(string digits) {
 ? ?vectorresult;
 ? ?if(digits.empty())
 ?  {
 ? ? ? ?return result;
 ?  }
 ? ?unordered_mapsymbolValues={
 ? ? ?  {'2',"abc"},
 ? ? ?  {'3',"def"},
 ? ? ?  {'4',"ghi"},
 ? ? ?  {'5',"jk"},
 ? ? ?  {'6',"mno"},
 ? ? ?  {'7',"pqrs"},
 ? ? ?  {'8',"tuv"},
 ? ? ?  {'9',"wxyz"},
 ?  }; 
 ? ?string combination;
 ? ?backtrack(result,symbolValues,digits,0,combination);
 ? ?return result;
}

代碼解釋

主體函數(shù)就是backtrack函數(shù)，傳入的值分別是最后結(jié)果列表、鍵值對、數(shù)字列表、第幾層（我理解是解空間樹的第幾層，也就是第幾個數(shù)字），combination就是數(shù)字對應(yīng)的每一個字母（2：abc）

用一個具體例子來解釋代碼運行過程，以23為例子

寫的可能不是很清楚，我是這樣一步一步走代碼，理解代碼的意思，實在是太菜了，只能先看懂別人的代碼和思想，再繼續(xù)前進(jìn)。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：力扣題庫電話號碼的字母組合-創(chuàng)新互聯(lián)
文章URL：http://muchs.cn/article18/dhehgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機網(wǎng)站建設(shè)、移動網(wǎng)站建設(shè)、用戶體驗、品牌網(wǎng)站建設(shè)、商城網(wǎng)站、網(wǎng)站制作

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容