AnyJohn 的网络博客

17. Lexicographical Letter Combinations of Phone Digits

Properties1
tags算法, 回溯, 递归, hackerrank

5分钟阅读

17. Lexicographical Letter Combinations of Phone Digits

Origin: Lexicographical Letter Combinations of Phone Digits

Given a string of digits where ‘2’-‘9’ map to letters (like on a phone keypad) and ‘0’,‘1’ map to themselves, return all possible letter combinations in lexicographical order.

Mapping:

  • ‘2’ → [a, b, c]
  • ‘3’ → [d, e, f]
  • ‘4’ → [g, h, i]
  • ‘5’ → [j, k, l]
  • ‘6’ → [m, n, o]
  • ‘7’ → [p, q, r, s]
  • ‘8’ → [t, u, v]
  • ‘9’ → [w, x, y, z]
  • ‘0’ → [‘0’]
  • ‘1’ → [‘1’]

Example 1

Input: digits = “23”

Output: [‘ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]

Explanation: ‘2’ → [a, b, c], ‘3’ → [d, e, f]. For each letter of ‘2’, combine with each letter of ‘3’.

Example 2

Input: digits = “203”

Output: [‘a0d’, ‘a0e’, ‘a0f’, ‘b0d’, ‘b0e’, ‘b0f’, ‘c0d’, ‘c0e’, ‘c0f’]

Explanation: ‘2’ → [a, b, c], ‘0’ → [‘0’], ‘3’ → [d, e, f]. For each letter of ‘2’, insert ‘0’, then combine with each letter of ‘3’.

Input Format

A string digits containing only characters ‘0’-‘9’.

Constraints

  • 0 <= digits.length <= 10
  • digits[i] is one of ‘0’-‘9’

Output Format

Return a STRING_ARRAY of all combinations, separated by spaces, in lexicographical order.

Sample Input 0

23

Sample Output 0

ad ae af bd be bf cd ce cf

Sample Input 1

203

Sample Output 1

a0d a0e a0f b0d b0e b0f c0d c0e c0f

函数契约

// 输入：digits（字符串，只含 '0'-'9'）
// 输出：所有可能的字母组合列表，字典序
// 边界：空字符串 → [] 或 [""]；单个数字 → 对应字母列表

边界表

场景返回什么
空字符串[] 或 [""]
单个数字 “2”[a, b, c]
“0” 或 “1”[“0”] 或 [“1”]
“23”9 个组合
正常场景所有组合的笛卡尔积

Resolution

我的解法

function letterCombinations(digits: string): string[] {
    if (!digits || digits.length === 0) {
        return []
    }
 
    const result: string[] = []
    const letterMap: { [key: string]: string[] } = {
        "0": ["0"],
        "1": ["1"],
        "2": ["a", "b", "c"],
        "3": ["d", "e", "f"],
        "4": ["g", "h", "i"],
        "5": ["j", "k", "l"],
        "6": ["m", "n", "o"],
        "7": ["p", "q", "r", "s"],
        "8": ["t", "u", "v"],
        "9": ["w", "x", "y", "z"]
    }
 
    const backtrack = (index: number, path: string) => {
        if (index === digits.length) {
            result.push(path)
            return
        }
        const letters = letterMap[digits[index]]
        for (const letter of letters) {
            backtrack(index + 1, path + letter)
        }
    }
    backtrack(0, "")
    return result
}

解题思路

经典回溯。对每个数字，从它对应的字母列表里选一个，拼接到 path，递归下一个数字。

  1. 建数字到字母的映射表（注意 7 和 9 是四个字母，0 和 1 映射到自身）
  2. backtrack(index, path)：index 是当前处理到第几个数字，path 是当前拼接的字符串
  3. index 等于 digits.length 时，path 就是一个完整组合，存入结果
  4. 否则遍历当前数字对应的字母，逐个递归

对比标准解法

标准解法有两种写法：

回溯（和你的解法一致）：

def letterCombinations(digits):
    if not digits: return []
    d = ["abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
    result = []
    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        for letter in d[int(digits[index])-2]:
            backtrack(index + 1, path + letter)
    backtrack(0, "")
    return result

区别：标准解法用索引偏移（int(digits[index])-2）访问数组，省了建 Map 的步骤。你的用 Map 更直观，可读性更好，两者性能一样。

迭代法（非递归）：

def letterCombinations(digits):
    if not digits: return []
    d = ["abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
    result = [""]
    for digit in digits:
        letters = d[int(digit)-2]
        result = [a + b for a in result for b in letters]
    return result

迭代法不需要递归栈，思路是：每处理一个数字，把已有结果和当前字母列表做笛卡尔积。比如 result = [“a”,“b”,“c”]，处理 ‘3’，变成 [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]。

你的回溯解法和标准解法完全一致，面试够用。迭代法作为了解，面试时如果面试官追问”能不能不用递归”，你可以写出迭代版。

复杂度

  • 时间：O(4^n)，每个数字最多 4 个字母，n 个数字
  • 空间：O(n)，递归栈深度

测试用例

输入输出场景
”23”9 个组合基本用例
""[]空字符串
”2”[a,b,c]单数字
”0”[“0”]数字 0
”1”[“1”]数字 1
”7”[p,q,r,s]四字母数字

全部通过。

参考来源

关系图谱

反向链接

近期发布