付費限定文章

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

Isaac Smith on Unsplash

題目敘述

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

例如輸入digits="23"

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

題目的原文敘述

測試範例

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深度優先 + 回溯法的技巧與模板。

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

若遇到終止條件 或滿足指定需求：

則 更新結果