Kotlin如何不使用嵌套循环统计两等长字符串不同索引处匹配字符数量

实现思路 #

要避免嵌套循环，我们可以通过O(n)时间复杂度的线性遍历完成统计，核心逻辑如下：

• 首先统计两个字符串相同索引位置字符相等的数量，记为samePosCount
• 分别统计两个字符串中每个字符的出现频次，得到两个频数字典
• 计算两个字符串中所有共同字符的总数量（每个字符取两个串中出现次数的较小值求和），记为totalCommonCount
• 最终结果 = 总共同字符数 - 同位置相等字符数，得到的就是字符相同但所处索引位置不同的总个数

代码实现 #

fun countDiffPosSameChar(s1: String, s2: String): Int {
    require(s1.length == s2.length) { "两个字符串长度必须相同" }
    
    var samePosCount = 0
    val freqS1 = mutableMapOf<Char, Int>()
    val freqS2 = mutableMapOf<Char, Int>()

    // 单次遍历完成同位置计数和频次统计，无嵌套循环
    for (index in s1.indices) {
        val c1 = s1[index]
        val c2 = s2[index]
        if (c1 == c2) samePosCount++
        freqS1[c1] = freqS1.getOrDefault(c1, 0) + 1
        freqS2[c2] = freqS2.getOrDefault(c2, 0) + 1
    }

    // 计算总共同字符数
    val totalCommonCount = freqS1.keys.sumOf { char ->
        minOf(freqS1[char]!!, freqS2.getOrDefault(char, 0))
    }

    return totalCommonCount - samePosCount
}

测试示例 #

• 输入：s1 = "abc", s2 = "bca"，输出：3，所有字符都相同且位置不同
• 输入：s1 = "aab", s2 = "aba"，输出：2，有2个字符相同但位置不同
• 输入：s1 = "abc", s2 = "abc"，输出：0，所有相同字符都在同一位置

内容的提问来源于stack exchange，提问作者Ta3ik