当前位置：首页 > news >正文

每日算法 -【Swift 算法】电话号码字母组合

news 2025/7/4 2:53:49

🚀 LeetCode 字符串数字映射（Swift）——电话号码字母组合

在日常刷题或面试中，我们经常会遇到字符串 + 回溯组合的问题。这道经典题——电话号码的字母组合 就是典型代表。本文将带你用 Swift 实现这道题，思路清晰，代码可复用，适合初学者和进阶者。

📌 题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

每个数字映射到一些字母，和电话按键类似：

2 → abc  
3 → def  
4 → ghi  
5 → jkl  
6 → mno  
7 → pqrs  
8 → tuv  
9 → wxyz

🧨 注意：

数字 1 和 0 不对应任何字母，应直接丢弃忽略。
返回所有可能的组合，顺序不限。

🧠 解题思路

使用 回溯算法（Backtracking）构造所有组合路径。
构造一个 数字到字母的映射字典。
从第一个数字开始递归，每次递归选择当前数字对应的所有字母之一，继续向下拼接。
一旦组合的长度等于有效数字长度（不含 0 和 1），就加入结果集。

🧑‍💻 Swift 实现

class Solution {func letterCombinations(_ digits: String) -> [String] {// 数字到字母的映射表（电话按键）let phoneMap: [Character: String] = ["2": "abc", "3": "def", "4": "ghi","5": "jkl", "6": "mno", "7": "pqrs","8": "tuv", "9": "wxyz"]// 过滤掉无效字符（只保留2~9）let filteredDigits = digits.filter { phoneMap.keys.contains($0) }guard !filteredDigits.isEmpty else {return [] // 全是0或1时，直接返回空数组}var result: [String] = []// 回溯函数：index表示当前处理的位置，path是当前已生成的组合func backtrack(_ index: Int, _ path: String) {// 如果已组合的长度等于有效数字长度，表示组合完成if index == filteredDigits.count {result.append(path)return}// 当前数字let digit = filteredDigits[filteredDigits.index(filteredDigits.startIndex, offsetBy: index)]// 对应的所有字母let letters = phoneMap[digit]!// 遍历所有字母，递归处理下一个位置for letter in letters {backtrack(index + 1, path + String(letter))}}// 从第0位开始回溯backtrack(0, "")return result}
}

🧪 测试示例

let solution = Solution()
print(solution.letterCombinations("23"))
print(solution.letterCombinations("1039"))

⏱ 时间复杂度分析

设有效输入数字长度为 n：

每个数字最多对应 4 个字母。
整体组合数量最多为 4^n。

时间复杂度：

O(4^n * n)

空间复杂度：

O(n * 4^n)

✅ 总结

本题是典型的回溯应用，适合练习组合类题目。
对 0 和 1 的处理需特别注意。
实际应用中也非常有参考价值。

🔁 拓展思考与实现

💡 1. 字典序排序

return result.sorted()

💡 2. 非递归实现

func letterCombinationsIterative(_ digits: String) -> [String] {let phoneMap: [Character: String] = ["2": "abc", "3": "def", "4": "ghi","5": "jkl", "6": "mno", "7": "pqrs","8": "tuv", "9": "wxyz"]var queue: [String] = [""]for digit in digits {guard let letters = phoneMap[digit] else { continue }var newQueue: [String] = []for prefix in queue {for letter in letters {newQueue.append(prefix + String(letter))}}queue = newQueue}return queue.count > 1 || queue[0] != "" ? queue : []
}

💡 3. 自定义映射支持

func letterCombinations(_ digits: String, withMapping mapping: [Character: String]) -> [String] {let filteredDigits = digits.filter { mapping.keys.contains($0) }guard !filteredDigits.isEmpty else { return [] }var result: [String] = []func backtrack(_ index: Int, _ path: String) {if index == filteredDigits.count {result.append(path)return}let digit = filteredDigits[filteredDigits.index(filteredDigits.startIndex, offsetBy: index)]for letter in mapping[digit]! {backtrack(index + 1, path + String(letter))}}backtrack(0, "")return result
}