付費限定

DFS模擬 撥號鍵盤上的英文子母組合Letter Comb of Phone Num Leetcode #17 精選75

更新於 發佈於 閱讀時間約 10 分鐘

題目敘述

題目會給我們一個傳統手機的數字鍵盤 和一個數字鍵的輸入字串digits,要求我們列舉出所有輸入字串digits可能對應到的英文字母的排列。

例如輸入digits="23"

那對應到的英文字母排列就是"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"

raw-image

題目的原文敘述


測試範例

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

約束條件

Constraints:

  • 0 <= digits.length <= 4

輸入字串digits的長度介於0~4,所有輸入有可能是空字串,請留意!

  • digits[i] is a digit in the range ['2', '9'].

digits 內部可能的數字範圍為'2' ~ '9'


演算法 DFS + 回溯法

基本上,看到枚舉類的題目,例如展開所有子集合、所有C(n,k)的組合、所有n!的直線排列... 等等需要列舉所有可能情況的題目,往往很適合使用DFS深度優先 + 回溯法的技巧與模板。

整個抽象化的思考框架和演算法範本如下


若遇到終止條件 或滿足指定需求:
則 更新結果


以行動支持創作者!付費即可解鎖
本篇內容共 4128 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/06/06
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
看更多
你可能也想看
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
全球科技產業的焦點,AKA 全村的希望 NVIDIA,於五月底正式發布了他們在今年 2025 第一季的財報 (輝達內部財務年度為 2026 Q1,實際日曆期間為今年二到四月),交出了打敗了市場預期的成績單。然而,在銷售持續高速成長的同時,川普政府加大對於中國的晶片管制......
Thumbnail
全球科技產業的焦點,AKA 全村的希望 NVIDIA,於五月底正式發布了他們在今年 2025 第一季的財報 (輝達內部財務年度為 2026 Q1,實際日曆期間為今年二到四月),交出了打敗了市場預期的成績單。然而,在銷售持續高速成長的同時,川普政府加大對於中國的晶片管制......
Thumbnail
重點摘要: 6 月繼續維持基準利率不變,強調維持高利率主因為關稅 點陣圖表現略為鷹派,收斂 2026、2027 年降息預期 SEP 連續 2 季下修 GDP、上修通膨預測值 --- 1.繼續維持利率不變,強調需要維持高利率是因為關稅: 聯準會 (Fed) 召開 6 月利率會議
Thumbnail
重點摘要: 6 月繼續維持基準利率不變,強調維持高利率主因為關稅 點陣圖表現略為鷹派,收斂 2026、2027 年降息預期 SEP 連續 2 季下修 GDP、上修通膨預測值 --- 1.繼續維持利率不變,強調需要維持高利率是因為關稅: 聯準會 (Fed) 召開 6 月利率會議
Thumbnail
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
Thumbnail
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
Thumbnail
題目敘述: 給定一個傳統手機鍵盤,如圖所示 接著給定一個字串word。 現在讓你重新安排每個字母的所在位置,每個字母可以重新安排到2~9這幾個鍵盤上的位置,每個字母限定只能選擇一個數字鍵去對應。 請問重新安排之後,最少要幾次按鍵才能輸出字串word?
Thumbnail
題目敘述: 給定一個傳統手機鍵盤,如圖所示 接著給定一個字串word。 現在讓你重新安排每個字母的所在位置,每個字母可以重新安排到2~9這幾個鍵盤上的位置,每個字母限定只能選擇一個數字鍵去對應。 請問重新安排之後,最少要幾次按鍵才能輸出字串word?
Thumbnail
題目敘述 題目會給我們一個字串s。 要求我們移除字串中的星號,還有刪除星號左手邊最靠近的第一個字元。 以字串的形式返回輸出答案。 題目的原文敘述 測試範例 Example 1: Input: s = "leet**cod*e" Output: "lecoe" Explanation:
Thumbnail
題目敘述 題目會給我們一個字串s。 要求我們移除字串中的星號,還有刪除星號左手邊最靠近的第一個字元。 以字串的形式返回輸出答案。 題目的原文敘述 測試範例 Example 1: Input: s = "leet**cod*e" Output: "lecoe" Explanation:
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定我們一個字串s,要求我們反轉字串s中所有母音字元的順序,並且以字串的形式輸出。 註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U 題目的原文敘述 測試範例 Example 1: Input: s = "hello" Output: "ho
Thumbnail
題目敘述 題目會給定我們一個字串s,要求我們反轉字串s中所有母音字元的順序,並且以字串的形式輸出。 註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U 題目的原文敘述 測試範例 Example 1: Input: s = "hello" Output: "ho
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給我們兩個輸入,字串s和字串t,要求我們判定s是否為t的子序列(Subsequence)? 題目的原文敘述 測試範例 Example 1: Input: s = "abc", t = "ahbgdc" Output: true Example 2: Input:
Thumbnail
題目敘述 題目會給我們兩個輸入,字串s和字串t,要求我們判定s是否為t的子序列(Subsequence)? 題目的原文敘述 測試範例 Example 1: Input: s = "abc", t = "ahbgdc" Output: true Example 2: Input:
Thumbnail
題目敘述 題目會給我們一個參數k 和 目標值n。 請問我們從1~9內挑k個相異的數字,使得他們的總和為n 的組合數有多少? 挑選時,每個數字必須相異,而且每個數字只能選一次。 題目的原文敘述 測試範例 Example 1: Input: k = 3, n = 7 Output: [
Thumbnail
題目敘述 題目會給我們一個參數k 和 目標值n。 請問我們從1~9內挑k個相異的數字,使得他們的總和為n 的組合數有多少? 挑選時,每個數字必須相異,而且每個數字只能選一次。 題目的原文敘述 測試範例 Example 1: Input: k = 3, n = 7 Output: [
Thumbnail
題目敘述 題目會給我們一個傳統手機的數字鍵盤 和一個數字鍵的輸入字串digits,要求我們列舉出所有輸入字串digits可能對應到的英文字母的排列。 例如輸入digits="23" 那對應到的英文字母排列就是"ad", "ae", "af", "bd", "be", "bf", "cd", "
Thumbnail
題目敘述 題目會給我們一個傳統手機的數字鍵盤 和一個數字鍵的輸入字串digits,要求我們列舉出所有輸入字串digits可能對應到的英文字母的排列。 例如輸入digits="23" 那對應到的英文字母排列就是"ad", "ae", "af", "bd", "be", "bf", "cd", "
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News