OpenHarmony KMP电话号码字母组合生成器 | 代码解析

2401_87681450

733人浏览 · 2025-12-06 22:31:50

2401_87681450 · 2025-12-06 22:31:50 发布

在这里插入图片描述

摘要

电话号码的字母组合生成器实现了给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合的功能。本文详细解析了输入解析、数字到字母映射、回溯法、迭代法等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射与电话按键相同。

示例：

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

1.2 应用场景

密码生成
字符串组合
排列组合问题
算法竞赛

2. 核心算法原理

2.1 回溯法

使用递归回溯的方式，逐步构建字母组合，到达字符串末尾时保存结果。时间复杂度 O(3^m × 4^n)，空间复杂度 O(m+n)。

2.2 迭代法

逐步扩展结果集，每次添加新数字对应的字母组合。时间复杂度 O(3^m × 4^n)，空间复杂度 O(3^m × 4^n)。

3. 代码实现详细解析

3.1 输入解析和验证

var digits: String? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("digits=", ignoreCase = true) -> {
                digits = line.substringAfter("=").trim()
            }
        }
    }

if (digits == null) {
    // 尝试直接使用输入作为数字字符串
    val lines = payload.lines().map { it.trim() }.filter { it.isNotEmpty() }
    if (lines.isNotEmpty()) {
        digits = lines[0]
    }
}

// 验证输入只包含 2-9
if (!digitStr.all { it in '2'..'9' }) {
    return "❌ 输入只能包含数字 2-9"
}

代码解析：

这段代码实现了灵活的输入解析和验证机制。首先声明一个可空字符串变量 digits，用于存储解析后的数字字符串。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，如果行以 digits= 开头（忽略大小写），提取等号后面的部分作为数字字符串。如果解析后数字字符串为 null，则尝试直接使用输入的第一行作为数字字符串，这种备选方案提高了输入格式的灵活性。

接下来进行输入验证。使用 all 函数检查字符串中的所有字符是否都在 ‘2’ 到 ‘9’ 的范围内。all 是 Kotlin 集合的高阶函数，接受一个谓词函数，返回布尔值表示所有元素是否都满足条件。这里使用 it in '2'..'9' 作为谓词，检查每个字符是否在指定范围内。

如果验证失败，返回错误信息。这种验证确保了算法只处理有效的输入，避免了后续处理中的异常。

3.2 数字到字母映射

val digitToLetters = mapOf(
    '2' to "abc",
    '3' to "def",
    '4' to "ghi",
    '5' to "jkl",
    '6' to "mno",
    '7' to "pqrs",
    '8' to "tuv",
    '9' to "wxyz"
)

代码解析：

这段代码定义了数字到字母的映射表，使用 mapOf 创建一个不可变映射。映射的键是数字字符（‘2’ 到 ‘9’），值是对应的字母字符串。这个映射遵循传统的电话按键布局：

数字 2 对应字母 “abc”
数字 3 对应字母 “def”
数字 4 对应字母 “ghi”
数字 5 对应字母 “jkl”
数字 6 对应字母 “mno”
数字 7 对应字母 “pqrs”（4 个字母）
数字 8 对应字母 “tuv”
数字 9 对应字母 “wxyz”（4 个字母）

注意数字 7 和 9 有 4 个字母，其他数字有 3 个字母。这种映射表的设计简洁明了，使得后续算法可以方便地查找每个数字对应的字母。

3.3 回溯法实现

fun letterCombinationsBacktrack(digits: String): List<String> {
    if (digits.isEmpty()) return emptyList()

    val results = mutableListOf<String>()

    fun backtrack(index: Int, current: StringBuilder) {
        if (index == digits.length) {
            results.add(current.toString())
            return
        }

        val digit = digits[index]
        val letters = digitToLetters[digit] ?: return

        for (letter in letters) {
            current.append(letter)
            backtrack(index + 1, current)
            current.setLength(current.length - 1)
        }
    }

    backtrack(0, StringBuilder())
    return results
}

代码解析：

这是回溯法的核心实现，使用递归回溯的方式生成所有可能的字母组合。函数首先检查输入是否为空，如果为空，直接返回空列表。

然后创建一个可变列表 results 用于存储所有生成的字母组合。

接下来定义内部递归函数 backtrack，它接受两个参数：index 是当前处理的数字索引，current 是当前正在构建的字母组合（使用 StringBuilder 提高字符串拼接效率）。

在递归函数内部，首先检查是否已经处理完所有数字。如果 index == digits.length，说明已经到达字符串末尾，当前构建的字母组合是完整的，将其添加到结果列表中并返回。这是递归的终止条件。

然后获取当前数字对应的字母字符串：val digit = digits[index] 获取当前索引位置的数字字符，val letters = digitToLetters[digit] ?: return 从映射表中查找对应的字母字符串。如果找不到（虽然理论上不应该发生），直接返回。

接下来遍历当前数字对应的所有字母。对于每个字母，执行以下步骤：

将字母添加到当前组合：current.append(letter)
递归处理下一个数字：backtrack(index + 1, current)，这会继续构建组合
回溯：current.setLength(current.length - 1)，移除刚才添加的字母，恢复到之前的状态，以便尝试下一个字母

这个回溯步骤是关键：通过移除刚才添加的字母，算法可以尝试当前数字对应的其他字母，生成不同的组合。

最后，从索引 0 和空的 StringBuilder 开始递归调用，返回所有生成的字母组合。

这个算法的时间复杂度是 O(3^m × 4^n)，其中 m 是对应 3 个字母的数字个数，n 是对应 4 个字母的数字个数（通常是数字 7 和 9）。空间复杂度是 O(m+n)，主要用于递归调用栈和当前构建的字符串。

3.4 迭代法实现

fun letterCombinationsIterative(digits: String): List<String> {
    if (digits.isEmpty()) return emptyList()

    var results = listOf("")

    for (digit in digits) {
        val letters = digitToLetters[digit] ?: continue
        val newResults = mutableListOf<String>()

        for (result in results) {
            for (letter in letters) {
                newResults.add(result + letter)
            }
        }

        results = newResults
    }

    return results
}

代码解析：

这是迭代法的核心实现，通过逐步扩展结果集的方式生成所有可能的字母组合。函数首先检查输入是否为空，如果为空，直接返回空列表。

然后初始化结果列表为一个包含空字符串的列表：var results = listOf("")。这个初始值很重要，它代表还没有处理任何数字时的基础状态。

接下来遍历输入字符串中的每个数字。对于每个数字，首先从映射表中获取对应的字母字符串。如果找不到，使用 continue 跳过当前数字。

然后创建一个新的结果列表 newResults，用于存储扩展后的组合。

接下来使用双重循环扩展结果集：

外层循环遍历当前的所有结果组合
内层循环遍历当前数字对应的所有字母

对于每个现有结果和每个字母，将字母添加到结果后面，形成新的组合：newResults.add(result + letter)。这种笛卡尔积的方式确保所有可能的组合都被生成。

处理完当前数字后，用新的结果列表替换旧的结果列表：results = newResults。这样，下一轮循环时，结果列表已经包含了当前数字的所有可能组合。

当所有数字都处理完毕后，返回最终的结果列表。这个算法的时间复杂度也是 O(3^m × 4^n)，但空间复杂度是 O(3^m × 4^n)，因为需要存储所有中间结果。

3.5 回溯过程分析

fun backtrackWithSteps(index: Int, current: StringBuilder, path: MutableList<String>) {
    if (index == digitStr.length) {
        steps.add("完成组合: \"${current.toString()}\"")
        return
    }

    val digit = digitStr[index]
    val letters = digitToLetters[digit] ?: return

    steps.add("处理数字 '$digit' (位置 $index): 可选字母 ${letters.toList().joinToString(", ") { "'$it'" }}")

    for (letter in letters) {
        steps.add("  选择字母 '$letter'")
        current.append(letter)
        backtrackWithSteps(index + 1, current, path)
        current.setLength(current.length - 1)
    }
}