如何检测字符串中的多处变更位置？Kotlin代码优化求助

你的问题出在原代码仅对比相同索引的单词，且只保留最后一处差异，同时未处理两个单词数组长度不同的情况（比如新字符串多了"two"）。要识别所有变更，需要覆盖修改、添加、删除三类差异，推荐以下两种实现方案：

方法一：双指针逐段对比（手动实现） #

将字符串拆分为单词列表后，用双指针遍历两个列表，处理所有差异场景：

fun findWordDifferences(oldStr: String, newStr: String): List<Pair<String?, String?>> {
    val oldWords = oldStr.split(" ")
    val newWords = newStr.split(" ")
    val differences = mutableListOf<Pair<String?, String?>>()
    
    var i = 0 // 旧单词列表指针
    var j = 0 // 新单词列表指针
    
    while (i < oldWords.size || j < newWords.size) {
        when {
            i >= oldWords.size -> {
                // 新列表存在新增单词
                differences.add(null to newWords[j])
                j++
            }
            j >= newWords.size -> {
                // 旧列表存在删除单词
                differences.add(oldWords[i] to null)
                i++
            }
            oldWords[i] == newWords[j] -> {
                // 单词匹配，跳过
                i++
                j++
            }
            else -> {
                // 尝试寻找后续匹配项，区分插入/删除场景
                val nextOldMatch = newWords.indexOf(oldWords[i], j)
                val nextNewMatch = oldWords.indexOf(newWords[j], i)
                
                if (nextOldMatch != -1 && (nextNewMatch == -1 || nextOldMatch < nextNewMatch)) {
                    // 新列表插入了单词
                    for (k in j until nextOldMatch) {
                        differences.add(null to newWords[k])
                    }
                    j = nextOldMatch
                } else if (nextNewMatch != -1) {
                    // 旧列表删除了单词
                    for (k in i until nextNewMatch) {
                        differences.add(oldWords[k] to null)
                    }
                    i = nextNewMatch
                } else {
                    // 单词修改
                    differences.add(oldWords[i] to newWords[j])
                    i++
                    j++
                }
            }
        }
    }
    return differences
}

// 调用示例
val oldString = "My friend gave me a gift"
val newString = "My father gave me two gifts"
val diffs = findWordDifferences(oldString, newString)

diffs.forEachIndexed { index, (old, new) ->
    when {
        old != null && new != null -> println("位置${index+1}：修改 '$old' → '$new'")
        old != null -> println("位置${index+1}：删除 '$old'")
        new != null -> println("位置${index+1}：添加 '$new'")
    }
}

运行输出：

位置2：修改 'friend' → 'father'
位置5：删除 'a'
位置6：添加 'two'
位置7：修改 'gift' → 'gifts'

方法二：最长公共子序列(LCS)算法精准定位 #

通过计算两个单词列表的最长公共子序列，对比原序列和LCS，明确所有差异：

fun computeLCS(oldWords: List<String>, newWords: List<String>): List<String> {
    val m = oldWords.size
    val n = newWords.size
    val dp = Array(m + 1) { Array(n + 1) { 0 } }
    
    // 填充DP表
    for (i in 1..m) {
        for (j in 1..n) {
            dp[i][j] = if (oldWords[i-1] == newWords[j-1]) {
                dp[i-1][j-1] + 1
            } else {
                maxOf(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    
    // 回溯获取LCS
    val lcs = mutableListOf<String>()
    var i = m
    var j = n
    while (i > 0 && j > 0) {
        if (oldWords[i-1] == newWords[j-1]) {
            lcs.add(oldWords[i-1])
            i--
            j--
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--
        } else {
            j--
        }
    }
    return lcs.reversed()
}

fun findDifferencesWithLCS(oldStr: String, newStr: String): List<Pair<String?, String?>> {
    val oldWords = oldStr.split(" ")
    val newWords = newStr.split(" ")
    val lcs = computeLCS(oldWords, newWords)
    val differences = mutableListOf<Pair<String?, String?>>()
    
    var oldIdx = 0
    var newIdx = 0
    var lcsIdx = 0
    
    while (oldIdx < oldWords.size || newIdx < newWords.size) {
        when {
            lcsIdx < lcs.size && oldIdx < oldWords.size && oldWords[oldIdx] == lcs[lcsIdx] && newIdx < newWords.size && newWords[newIdx] == lcs[lcsIdx] -> {
                // 匹配LCS，跳过
                oldIdx++
                newIdx++
                lcsIdx++
            }
            oldIdx < oldWords.size && (lcsIdx >= lcs.size || oldWords[oldIdx] != lcs[lcsIdx]) -> {
                // 旧列表删除单词
                differences.add(oldWords[oldIdx] to null)
                oldIdx++
            }
            newIdx < newWords.size && (lcsIdx >= lcs.size || newWords[newIdx] != lcs[lcsIdx]) -> {
                // 新列表添加单词
                differences.add(null to newWords[newIdx])
                newIdx++
            }
            else -> {
                // 单词修改
                differences.add(oldWords[oldIdx] to newWords[newIdx])
                oldIdx++
                newIdx++
            }
        }
    }
    return differences
}

// 调用示例
val diffsLCS = findDifferencesWithLCS(oldString, newString)
diffsLCS.forEachIndexed { index, (old, new) ->
    when {
        old != null && new != null -> println("位置${index+1}：修改 '$old' → '$new'")
        old != null -> println("位置${index+1}：删除 '$old'")
        new != null -> println("位置${index+1}：添加 '$new'")
    }
}

该方法能更精准处理连续添加/删除等复杂差异场景。

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