欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net

摘要

有效的字母异位词检测器实现了判断两个字符串是否为字母异位词的功能。字母异位词是指字母相同但顺序不同的字符串。本文详细解析了输入解析、字符计数法、排序比较法、字符频率统计、差异分析等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定两个字符串，判断它们是否为字母异位词。字母异位词是指由相同字母组成但顺序不同的字符串。

示例：

• 字符串1："anagram"
• 字符串2："nagaram"
• 结果：是字母异位词（都包含 3 个 ‘a’，1 个 ‘n’，1 个 ‘g’，1 个 ‘r’，1 个 ‘m’）

1.2 应用场景

• 密码验证
• 文本分析
• 字符串匹配
• 数据清洗
• 算法竞赛

2. 核心算法原理

2.1 字符计数法

统计两个字符串中每个字符的出现次数，如果所有字符的频率都相同，则是异位词。时间复杂度 O(n)，空间复杂度 O(k)，k 为字符种类数。

2.2 排序比较法

将两个字符串排序后比较，如果排序后的字符串相同，则是异位词。时间复杂度 O(n log n)，空间复杂度 O(n)。

3. 代码实现详细解析

3.1 输入解析模块

var str1: String? = null
var str2: String? = null

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

if (str1 == null || str2 == null) {
    // 尝试按行解析
    val lines = payload.lines().map { it.trim() }.filter { it.isNotEmpty() }
    if (lines.size >= 2) {
        str1 = lines[0]
        str2 = lines[1]
    }
}

代码解析：

这段代码实现了灵活的输入解析机制，支持两种输入格式。首先声明两个可空字符串变量 str1 和 str2，分别用于存储两个输入字符串。使用可空类型是因为这些参数可能不存在或解析失败，需要后续验证。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行，得到一个干净的字符串列表。这种链式调用是 Kotlin 中常见的处理集合的方式，代码简洁且易于理解。

接下来使用 forEach 遍历每一行，使用 when 表达式进行模式匹配。when 表达式是 Kotlin 中强大的条件判断结构，比传统的 if-else 链更简洁清晰。

第一个分支处理 str1= 格式的输入。使用 startsWith("str1=", ignoreCase = true) 检查行是否以 “str1=” 开头（忽略大小写），如果匹配，使用 substringAfter("=") 提取等号后面的部分作为第一个字符串，trim() 去除空白字符。

第二个分支处理 str2= 格式的输入，使用相同的方式提取第二个字符串。

如果解析后两个字符串都为 null，则尝试按行解析：将输入按行分割并过滤空行，如果至少有 2 行，则第一行作为 str1，第二行作为 str2。这种备选方案提高了输入格式的灵活性，用户可以直接输入两行字符串而不需要指定参数名。

3.2 长度预检查

if (s1.length != s2.length) {
    builder.appendLine("❌ 检测结果: 不是异位词")
    builder.appendLine("原因: 两个字符串长度不同 (${s1.length} vs ${s2.length})")
    return builder.toString().trim()
}

代码解析：

这段代码实现了快速的预检查，如果两个字符串长度不同，直接返回结果，避免不必要的计算。这是异位词检测的一个重要优化：由于异位词必须包含相同的字符，因此长度必须相同。如果长度不同，可以立即判断不是异位词，无需进行后续的字符统计和比较。

这种早期返回的优化可以显著提高算法效率，特别是在处理大量数据时。代码首先比较两个字符串的长度，如果不同，构建错误信息并立即返回，避免执行后续的字符统计和比较操作。

3.3 字符计数法实现

fun isAnagramByCount(s1: String, s2: String): Boolean {
    val count1 = s1.lowercase().groupingBy { it }.eachCount()
    val count2 = s2.lowercase().groupingBy { it }.eachCount()
    return count1 == count2
}

代码解析：

这是字符计数法的核心实现，通过统计字符频率来判断是否为异位词。函数首先对两个字符串进行处理：使用 lowercase() 将所有字符转换为小写，这样可以使检测不区分大小写。例如，"Anagram" 和 "nagaram" 会被识别为异位词。

然后使用 groupingBy { it } 对字符进行分组。groupingBy 是 Kotlin 集合的高阶函数，接受一个键选择器函数，返回一个分组对象。这里使用 { it } 表示按照字符本身进行分组，即相同的字符会被分到同一组。

接下来使用 eachCount() 计算每个分组中的元素个数，返回一个 Map<Char, Int>，其中键是字符，值是该字符出现的次数。这种链式调用方式使得代码非常简洁，一行代码就完成了字符频率统计。

例如，对于字符串 "anagram"，count1 可能是 {a=3, n=1, g=1, r=1, m=1}；对于字符串 "nagaram"，count2 也是 {a=3, n=1, g=1, r=1, m=1}。

最后比较两个频率映射是否相等。Kotlin 的 Map 类型重写了 equals 方法，如果两个映射包含相同的键值对（不考虑顺序），则认为相等。如果两个映射相等，说明所有字符的出现次数都相同，返回 true；否则返回 false。

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为需要遍历字符串进行统计。空间复杂度是 O(k)，其中 k 是字符种类数，因为需要存储每个字符的频率。在 ASCII 字符集中，k 最多为 128，因此空间复杂度可以视为 O(1)。

3.4 排序比较法实现

fun isAnagramBySort(s1: String, s2: String): Boolean {
    return s1.lowercase().toCharArray().sorted() == s2.lowercase().toCharArray().sorted()
}

代码解析：

这是排序比较法的核心实现，通过比较排序后的字符串来判断是否为异位词。函数首先对两个字符串进行处理：使用 lowercase() 将所有字符转换为小写，使检测不区分大小写。

然后使用 toCharArray() 将字符串转换为字符数组。字符数组是字符的序列，可以方便地进行排序操作。

接下来使用 sorted() 对字符数组进行排序。sorted() 是 Kotlin 集合的扩展函数，返回一个新的排序后的列表。排序算法通常是稳定的快速排序或归并排序，时间复杂度为 O(n log n)。

排序后，如果两个字符串是异位词，它们的排序结果应该完全相同。例如，"anagram" 排序后是 ['a', 'a', 'a', 'g', 'm', 'n', 'r']，"nagaram" 排序后也是 ['a', 'a', 'a', 'g', 'm', 'n', 'r']。

最后比较两个排序后的列表是否相等。Kotlin 的列表类型重写了 equals 方法，如果两个列表包含相同顺序的元素，则认为相等。如果相等，说明是异位词，返回 true；否则返回 false。

这个算法的优点是代码非常简洁，只需要一行代码就能实现。缺点是时间复杂度较高，为 O(n log n)，因为需要排序；空间复杂度也是 O(n)，因为需要存储排序后的字符数组。但对于较短的字符串，这种方法的性能差异并不明显，而且代码可读性更好。

3.5 字符频率统计和差异分析

val freq1Map = s1.lowercase().groupingBy { it }.eachCount()
val freq2Map = s2.lowercase().groupingBy { it }.eachCount()
val freq1 = freq1Map.toList().sortedBy { it.first }.toMap()
val freq2 = freq2Map.toList().sortedBy { it.first }.toMap()

builder.appendLine("📊 字符频率统计")
freq1.forEach { (char: Char, count: Int) ->
    builder.appendLine("  '$char': $count 次")
}

builder.appendLine("🔬 字符差异分析")
val allChars = (freq1.keys + freq2.keys).distinct().sorted()

if (isAnagramCount) {
    builder.appendLine("所有字符频率完全匹配:")
    allChars.forEach { char: Char ->
        val count1 = freq1[char] ?: 0
        val count2 = freq2[char] ?: 0
        builder.appendLine("  '$char': str1=$count1, str2=$count2 ✓")
    }
} else {
    builder.appendLine("字符频率差异:")
    allChars.forEach { char: Char ->
        val count1 = freq1[char] ?: 0
        val count2 = freq2[char] ?: 0
        if (count1 != count2) {
            val diff = if (count1 > count2) count1 - count2 else count2 - count1
            builder.appendLine("  '$char': str1=$count1, str2=$count2 ✗ (差异: $diff)")
        }
    }
}

代码解析：

这段代码实现了详细的字符频率统计和差异分析，帮助用户理解两个字符串中字符的分布情况。首先使用 groupingBy 和 eachCount() 统计两个字符串中每个字符的出现次数，得到两个频率映射。

然后将频率映射转换为排序后的映射，使得输出更加有序和易读。使用 toList() 将映射转换为列表，使用 sortedBy { it.first } 按键（字符）排序，然后使用 toMap() 转换回映射。

接下来输出字符频率统计信息。使用 forEach 遍历第一个字符串的频率映射，对每个字符输出其出现次数。使用解构声明 (char: Char, count: Int) 将键值对解构为两个变量，使代码更简洁。

然后进行字符差异分析。首先获取所有出现在两个字符串中的字符，使用 (freq1.keys + freq2.keys) 合并两个映射的键集合，使用 distinct() 去重，使用 sorted() 排序。

根据检测结果决定输出内容。如果是异位词，输出所有字符的频率匹配信息，显示每个字符在两个字符串中的出现次数，并使用 “✓” 标记表示匹配。

如果不是异位词，只输出存在差异的字符信息。对于每个字符，比较它在两个字符串中的出现次数。如果次数不同，计算差异值（使用条件表达式判断哪个更大，然后计算差值），输出差异信息并使用 “✗” 标记。

这种详细的输出对于教学和调试非常有用，用户可以清楚地看到两个字符串中字符的分布情况，理解为什么它们是或不是异位词。

3.6 排序对比展示

builder.appendLine("🔄 排序对比")
val sorted1 = s1.lowercase().toCharArray().sorted().joinToString("")
val sorted2 = s2.lowercase().toCharArray().sorted().joinToString("")
builder.appendLine("字符串1 排序后: \"$sorted1\"")
builder.appendLine("字符串2 排序后: \"$sorted2\"")
builder.appendLine("匹配: ${if (sorted1 == sorted2) "是 ✓" else "否 ✗"}")

代码解析：

这段代码实现了排序对比展示，直观地展示排序比较法的执行过程。首先将两个字符串转换为小写，然后转换为字符数组，进行排序，最后使用 joinToString("") 将排序后的字符数组连接成字符串。

joinToString("") 使用空字符串作为分隔符，将字符数组中的字符连接成一个字符串。这样可以得到排序后的字符串表示，例如 "anagram" 排序后是 "aaagmnr"。

然后输出排序后的两个字符串，以及它们是否匹配的信息。如果排序后的字符串相等，输出 “是 ✓”；否则输出 “否 ✗”。这种展示方式直观地展示了排序比较法的工作原理，帮助用户理解算法是如何通过排序来判断异位词的。

4. 算法复杂度分析

4.1 时间复杂度

• 字符计数法：O(n)，需要遍历字符串统计频率
• 排序比较法：O(n log n)，需要对字符数组排序
• 总体时间复杂度：O(n)（使用字符计数法）

4.2 空间复杂度

• 字符计数法：O(k)，k 为字符种类数（最多 128，可视为 O(1)）
• 排序比较法：O(n)，需要存储排序后的字符数组
• 总体空间复杂度：O(k) 或 O(1)（使用字符计数法）

5. 算法优化建议

5.1 字符计数法优化

字符计数法已经是时间最优的算法，时间复杂度为 O(n)。

5.2 空间优化

如果字符串只包含小写字母，可以使用数组代替哈希表，空间复杂度更明确。

5.3 预处理优化

对于需要多次检测的场景，可以预先计算字符频率，避免重复计算。

6. 应用场景扩展

1. 密码验证：检查两个密码是否使用相同的字符
2. 文本分析：查找文本中的异位词组合
3. 字符串匹配：模糊匹配相似字符串
4. 数据清洗：识别重复或相似的文本数据
5. 算法竞赛：LeetCode 等平台的经典问题

7. 总结

有效的字母异位词检测器实现了两种检测方法，核心要点：

1. 字符计数法：时间复杂度 O(n)，空间复杂度 O(k)，是最优算法
2. 排序比较法：代码简洁，但时间复杂度 O(n log n)
3. 长度预检查：快速排除长度不同的字符串，提高效率
4. 详细分析：提供字符频率统计、差异分析、排序对比等详细功能

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如密码验证、文本分析、字符串匹配等场景。字符计数法的思想也可以扩展到其他类似问题，如判断两个字符串是否包含相同的字符集等。