833. 字符串中的查找与替换 - Kotlin 排序+模拟

Problem: 833. 字符串中的查找与替换

思路

这道题需要考虑到的细节主要有两点：

• target中被替换的字符串的长度会与原子字符串不同，从而导致原字符串对应的下标发生变化，例如abc将a替换为aaa，则b的下标会从1变为3
• 由于替换是同时进行的，我们不能在被替换的字符串中寻找子字符串（由于题干保证了每组操作不会包含重叠的字符串，所以这点不需要考虑了）

对操作的索引indices进行排序，可以同时解决上面两个问题

• 当我们先对索引较小的子字符串进行替换操作时，即便仍然会影响下标的对应关系，但此时影响的是该子字符串后面的所有字符的对应关系，我们简单地可以用一个偏移值变量shift维护这个偏移关系，即每次令shift+=targets[i].length-sources[i].length
• 由于我们按索引升序进行替换操作，可以保证，在第i次操作后，indices[i]+shift+source[i].length（即被替换完的子字符串末尾处索引）左侧均已完成替换操作，接下来的操作中我们只需要在该索引右侧查找即可，避免了从被替换的字符串中寻找子字符串的情况（由于题干保证了每组操作不会包含重叠的字符串，所以这点不需要考虑了）

从str的indices[i]+shift索引处通过indexOf查找source[i]，如果结果等于indices[i]+shift则说明索引处存在该子字符串，直接进行替换操作即可

复杂度

• 时间复杂度: 快速排序平均时间复杂度为 ，字符串替换操作时间复杂度为

• 空间复杂度: 快速排序需要的空间复杂度为，字符串替换操作空间复杂度为

Code

class Solution {
    fun findReplaceString(s: String, indices: IntArray, sources: Array<String>, targets: Array<String>): String {
        quickSort(indices, sources, targets, 0, indices.size - 1)
        var shift = 0
        var str = s
        for (i in indices.indices) {
            if (str.indexOf(sources[i], indices[i] + shift) != indices[i] + shift) {
                continue
            }
            str = str.substring(0, indices[i] + shift) + targets[i] + str.substring(indices[i] + shift + sources[i].length)
            shift += targets[i].length - sources[i].length
        }
        return str
    }

    fun quickSort(indices: IntArray, sources: Array<String>, targets: Array<String>, beginIndex: Int, endIndex: Int) {
        if (beginIndex >= endIndex) return
        val mid = indices[beginIndex]
        var left = beginIndex
        var right = endIndex
        while (left < right) {
            while (indices[right] > mid && left < right) {
                right--
            }
            if (left < right) swap(indices, sources, targets, left++, right)
            while (indices[left] < mid && left < right) {
                left++
            }
            if (left < right) swap(indices, sources, targets, left, right--)
        }

        quickSort(indices, sources, targets, beginIndex, left - 1)
        quickSort(indices, sources, targets, left + 1, endIndex)
    }


    fun swap(indices: IntArray, sources: Array<String>, targets: Array<String>, a: Int, b: Int) {
        swap(indices, a, b)
        swap(sources, a, b)
        swap(targets, a, b)
    }

    fun swap(arr: IntArray, a: Int, b: Int) {
        val tmp = arr[a]
        arr[a] = arr[b]
        arr[b] = tmp
    }

    fun swap(arr: Array<String>, a: Int, b: Int) {
        val tmp = arr[a]
        arr[a] = arr[b]
        arr[b] = tmp
    }
}