資訊專欄INFORMATION COLUMN
摘要：題目要求也就是說，將數(shù)字對應(yīng)的字母的排列組合的的所有可能結(jié)果都枚舉出來，順序不唯一。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。這一種數(shù)據(jù)結(jié)構(gòu)通過來實(shí)現(xiàn)。相比于上一種思路中，內(nèi)存占用更小，而且更加靈活。
題目要求
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want.
也就是說，將數(shù)字對應(yīng)的字母的排列組合的的所有可能結(jié)果都枚舉出來，順序不唯一。
leetcode給這道題目加了一個標(biāo)簽很有意思，叫做Backtracking。點(diǎn)進(jìn)去之后又很多類似的題目。這種類型的題目一般需要求出上一種情況的前提下才可以得知下一種情況。比如我必須先得知按下“2”后所有字母的可能值，才能在計算出“22”對應(yīng)的可能值
思路一：遞歸當(dāng)我們無法直接得出結(jié)果的時候，我們可以借助遞歸讓計算機(jī)幫我們考慮每一種情況并逐級得出當(dāng)前的結(jié)果。在本思路中，我用了String數(shù)組來表示每一個按鍵對應(yīng)的字母，其中數(shù)組的下標(biāo)代表按鍵值。
String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List letterCombinations(String digits) {
List result = new ArrayList();
for(int i = 0 ; i letterCombinations(char digit, List currentList){
int number = digit - "0";
String letter = letters[number];
if(letter.length()==0){
return currentList;
}
if(currentList.size() == 0){
for(int i = 0 ; i result = new ArrayList();
for(int i = 0 ; i
思路二：隊(duì)列（通過linkedlist實(shí)現(xiàn)）
從隊(duì)列頭獲得上一種情況的結(jié)果，經(jīng)過處理后添加到隊(duì)列尾。這一種數(shù)據(jù)結(jié)構(gòu)通過linkedList來實(shí)現(xiàn)。相比于上一種思路中ArrayList，linkedList內(nèi)存占用更小，而且更加靈活。
String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List letterCombinations2(String digits) {
LinkedList l = new LinkedList();
if(digits.length()==0){
return l;
}
l.add("");
int empty = 0;
for(int i = 0 ; i < digits.length() ; i++){
int number = digits.charAt(i) - "0";
String letter = letters[number];
if(letter.length() == 0){
empty++;
continue;
}
while(l.peek().length() + empty == i){
String peek = l.removeFirst();
for(int j = 0 ; j
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67027.html
摘要：而按鍵和字母的對應(yīng)關(guān)系如上圖。這將成為下一次操作的前序字符串。對于每一個不同的前序字符串，我們都要在其后面分別加上當(dāng)前鍵所表示的不同字符，再將獲得的結(jié)果字符串加入里面。 題目詳情 Given a digit string, return all possible letter combinations that the number could represent. mapping o...
摘要：最新更新請見深度優(yōu)先搜索復(fù)雜度時間空間遞歸?？臻g思路首先建一個表，來映射號碼和字母的關(guān)系。然后對號碼進(jìn)行深度優(yōu)先搜索，對于每一位，從表中找出數(shù)字對應(yīng)的字母，這些字母就是本輪搜索的幾種可能。 Letter Combinations of a Phone Number 最新更新請見：https://yanjia.me/zh/2019/01/... Given a digit string...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
摘要：不過好消息是，在事件發(fā)生的二十四小時以后，我發(fā)現(xiàn)我的賬號解禁了，哈哈哈哈。 本文最初發(fā)布于我的個人博客：咀嚼之味 從昨天凌晨四點(diǎn)起，我的 Leetcode 賬號就無法提交任何代碼了，于是我意識到我的賬號大概是被封了…… 起因 我和我的同學(xué) @xidui 正在維護(hù)一個項(xiàng)目 xidui/algorithm-training。其實(shí)就是收錄一些算法題的解答，目前主要對象就是 Leetcode。...
閱讀 2767·2021-11-24 10:23
閱讀 1164·2021-11-17 09:33
閱讀 2512·2021-09-28 09:41
閱讀 1427·2021-09-22 15:55
閱讀 3649·2019-08-29 16:32
閱讀 1916·2019-08-29 16:25
閱讀 1065·2019-08-29 11:06
閱讀 3431·2019-08-29 10:55
