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

2024-03-12 HGNULB 约 14 分钟

文章信息 6 个分类 · 4 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 小米

标签

数组 字符串 哈希表 排序

目录 收起 展开

题目描述

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

题意分析

给定原字符串 s 和三个等长数组 indexes、sources、targets，第 $i$ 条替换规则的含义是：如果原串从下标 indexes[i] 开始的那一段恰好等于 sources[i]，就把这一段替换成 targets[i]；否则这条规则不生效，原样保留。返回执行完所有替换后的字符串。

「所有替换同时发生」是这道题的核心设定，它有两层含义。第一，每条规则的匹配判定都是在原字符串上进行的，不受其它替换的影响——你不能先做一次替换再拿改动后的串去匹配下一条。第二，每条规则给出的 indexes[i] 也是原字符串上的下标，前面的替换即使改变了长度，也不能挪动后面规则的位置。这两点合起来，意味着任何「按顺序在结果串上就地修改」的实现都是错的。

「不生效就原样保留」也要读细：匹配失败时，不仅 targets[i] 不写入，sources[i] 覆盖的那一段原文也要照常输出，不能被跳过。

约束里有两条关键保证：indexes 中的值互不相同，且题目保证所有替换操作互不重叠。这排除了「两条规则抢同一段字符」的歧义，让每个原串位置最多被一条规则占用，实现可以放心地线性推进。另外 $1 \le

s

\le 1000$、$1 \le k \le 100$，规模极小，$O(

s

\cdot k)$ 也能过——题目考的是语义正确性而非效率。

但 indexes 不保证有序——这是最容易踩的地方。规则可能以任意顺序给出，而输出必须按原串从左到右拼接，所以要么先排序，要么建立「下标 → 规则」的映射。

边界方面：某条规则的 sources[i] 可能比从该下标到串尾的剩余长度还长，此时必然匹配失败，取子串时不能越界；indexes 可能覆盖不到串的开头或结尾，未被任何规则触及的字符要原样输出。

解法：按索引排序 + 扫描拼接

核心思路

先看两个错误的方向，它们能解释这道题的坑在哪。第一个是「按给定顺序逐条在字符串上做替换」：只要有一条规则生效并改变了长度，后面所有规则的 indexes 就全部失准。第二个是「按 indexes 从大到小倒着替换」：这样长度变化只影响已处理的右侧，看似可行，但匹配判定仍然可能出错——如果某条规则的 target 恰好在原串中制造出另一条规则的 source 模式，倒序做也会误判。稳妥的做法是完全不修改原串，只做一次从左到右的扫描并把结果写进新缓冲区。

于是解法的骨架确定为：用一个指针 $p$ 在原串上单调右移，边走边决定当前位置该往输出缓冲区里写什么。 每一步只有两种可能——要么这里有一条生效的规则，写入 target 并把 $p$ 跳过整个 source 的长度；要么没有，写入 $s[p]$ 这一个字符并让 $p$ 前进一格。

要让这个扫描能在 $O(1)$ 时间判断「当前位置有没有规则」，就需要把规则按 indexes 升序排好。做法是建立一个下标序列 $order$，按 indexes 的值排序，然后用第二个指针 $t$ 指向「下一条尚未处理的规则」。因为 $p$ 单调右移、规则也按位置递增，$t$ 同样只需单调右移，两个指针各走一遍，是典型的双指针推进。

显式写下不变量：输出缓冲区里已经是原串前 $p$ 个字符经过全部相关替换后的结果；$order[t]$ 是所有起始位置不小于 $p$ 的规则中位置最靠前的那一条（若 $t$ 已越界则说明规则已用尽）。

每一轮的判断分三层：

• 当前位置没有规则（$t$ 越界，或 $indexes[order[t]] \ne p$）：写入 $s[p]$，$p$ 加一。
• 当前位置有规则且匹配成功：写入对应的 target，$p$ 前进 source 的长度，$t$ 加一。
• 当前位置有规则但匹配失败：写入 $s[p]$ 这一个字符，$p$ 加一，$t$ 也要加一。

第三种情形有两处细节值得强调。其一，匹配失败时 $p$ 只前进一格而不是 source 的长度——因为这条规则不生效，被它「盯上」的那段原文要完整输出，只能一格一格地走。其二，$t$ 仍然要加一——这条规则已经被判定过了，不能让它在下一轮重新触发；由于题目保证替换互不重叠，同一个位置不会有第二条规则，$t$ 前进不会漏掉任何东西。

匹配判定本身要先做长度检查再比内容：只有 $p +

source

\le

s

$ 时截取才合法。把长度检查放在前面，靠短路求值挡住越界，是这里的标准写法。

由于始终只读原串、只写新缓冲区，「同时发生」的语义天然成立——任何一条规则的判定都不会看到别的规则的产物。

解题步骤

• 第一步，建立规则下标序列 $order = [0, 1, \dots, k-1]$，按 indexes 的值升序排序。 为什么排序的是下标而不是直接排序三个数组：三个数组是按位置一一对应的，直接排任何一个都会破坏对应关系。排一个「间接下标」是处理平行数组的标准手法。为什么必须排序：题目不保证 indexes 有序，而输出必须按原串位置从左到右生成。
• 第二步，准备输出缓冲区、原串指针 $p = 0$、规则指针 $t = 0$。 为什么要用缓冲区而不是在原串上就地改：就地修改会让后续规则的 indexes 失准，也会让匹配判定看到别的替换的结果，直接违反「同时发生」。
• 第三步，当 $p$ 未到串尾时循环。 为什么循环条件用 $p$ 而不是 $t$：规则可能覆盖不到串尾，剩余字符必须继续输出；用 $t$ 作条件会在规则用尽时提前退出，丢掉后缀。
• 第四步，若 $t$ 未越界且 $indexes[order[t]] = p$，说明当前位置有一条待判定的规则。 为什么用相等判断而不是「小于等于」：$p$ 与 $t$ 都单调右移，且每条规则在其起始位置恰好被访问一次，所以只会精确相等。若出现 $indexes[order[t]] < p$，说明前面某步跳过了规则的起点，那是实现有误。

• **第五步，匹配判定：先查 $p +

  source

  \le

  s

  $，再比 $s$ 从 $p$ 开始的这一段是否等于 source。** 为什么长度检查必须在前：source 可能比剩余长度还长，先截取会越界。靠 && 的短路求值天然实现这个顺序。

• **第六步，匹配成功则写入 target，并令 $p$ 前进 $

  source

  $、$t$ 加一。** 为什么 $p$ 跳的是 source 的长度而不是 target 的长度：$p$ 走在原串上，被消费掉的是 source 这么多个原字符；target 只是写进缓冲区，与原串的推进无关。这是本题最容易写反的一行。

• 第七步，匹配失败则写入 $s[p]$ 单个字符，$p$ 加一、$t$ 加一。 为什么 $t$ 也要加一：这条规则已判定完毕且不生效，若不推进会在下一轮以 $p+1$ 与它的起始位置比较，虽然不再相等而落入普通分支，但 $t$ 会一直卡在这条废规则上，导致后面所有规则都无法被触发。
• 第八步，否则（当前位置无规则）写入 $s[p]$，$p$ 加一。
• 第九步，循环结束后把缓冲区转成字符串返回。

以 s = "abcd"、indexes = [0, 2]、sources = ["a", "cd"]、targets = ["eee", "ffff"] 走一遍（期望结果 "eeebffff"）。

排序：indexes 已是升序，$order = [0, 1]$。初始 $p = 0$、$t = 0$、缓冲区为空。

$p = 0$：$t = 0$ 未越界，$indexes[order[0]] = 0 = p$，有规则。source 是 "a"，长度检查 $0 + 1 \le 4$ 通过，比较 $s$ 从 0 开始的 1 个字符 "a" 与 source 相等，匹配成功。写入 target "eee"，缓冲区变成 "eee"；$p$ 前进 $

source

= 1$ 变成 1（不是 前进 target 的长度 3）；$t$ 变成 1。

$p = 1$：$t = 1$ 未越界，但 $indexes[order[1]] = 2 \ne 1$，无规则。写入 $s[1] = $ 'b'，缓冲区变成 "eeeb"；$p$ 变成 2。

$p = 2$：$indexes[order[1]] = 2 = p$，有规则。source 是 "cd"，长度检查 $2 + 2 \le 4$ 通过，比较 $s$ 从 2 开始的 2 个字符 "cd" 与 source 相等，匹配成功。写入 "ffff"，缓冲区变成 "eeebffff"；$p$ 前进 2 变成 4；$t$ 变成 2。

$p = 4$：等于串长，循环结束。返回 "eeebffff"。

这一步的关键观察是：第二条规则的 indexes 是 2，指的是原串中 "cd" 的位置；此刻缓冲区已经有 4 个字符了，如果按输出位置去对齐规则，就会完全错位。始终用 $p$ 在原串上定位，是「同时发生」语义的实现方式。

再看匹配失败的情形：s = "abcd"、indexes = [0, 2]、sources = ["ab", "ec"]、targets = ["eee", "ffff"]（期望结果 "eeecd"）。

$p = 0$：规则 0 的 source 是 "ab"，$s$ 从 0 开始的 2 个字符是 "ab"，匹配成功。写入 "eee"，$p$ 前进 2 变成 2，$t$ 变成 1。

$p = 2$：$indexes[order[1]] = 2 = p$，有规则。source 是 "ec"，长度检查 $2 + 2 \le 4$ 通过，但 $s$ 从 2 开始的 2 个字符是 "cd"，与 "ec" 不等，匹配失败。此时只写入 $s[2] = $ 'c' 这一个字符，缓冲区变成 "eeec"；$p$ 只前进一格变成 3；$t$ 变成 2。这里如果误让 $p$ 前进 $

source

= 2$，字符 'd' 就会被吞掉，结果变成 "eeec"，少了一位。

$p = 3$：$t = 2$ 已越界，无规则。写入 $s[3] = $ 'd'，缓冲区变成 "eeecd"；$p$ 变成 4，循环结束。

返回 "eeecd"。这个例子同时验证了「失败时只走一格」和「规则用尽后仍要输出剩余字符」两条。

代码实现

class Solution {
    public String findReplaceString(String s, int[] indexes, String[] sources, String[] targets) {
        int n = indexes.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (a, b) -> indexes[a] - indexes[b]);

        StringBuilder sb = new StringBuilder();
        int p = 0;
        int t = 0;
        while (p < s.length()) {
            if (t < n && p == indexes[order[t]]) {
                int k = order[t];
                String src = sources[k];
                if (p + src.length() <= s.length() && s.startsWith(src, p)) {
                    sb.append(targets[k]);
                    p += src.length();
                } else {
                    sb.append(s.charAt(p));
                    p++;
                }
                t++;
            } else {
                sb.append(s.charAt(p));
                p++;
            }
        }
        return sb.toString();
    }
}

func findReplaceString(s string, indexes []int, sources []string, targets []string) string {
    n := len(indexes)
    order := make([]int, n)
    for i := 0; i < n; i++ {
        order[i] = i
    }
    sort.Slice(order, func(i, j int) bool {
        return indexes[order[i]] < indexes[order[j]]
    })

    p := 0
    t := 0
    buf := make([]byte, 0, len(s))

    for p < len(s) {
        if t < n && p == indexes[order[t]] {
            k := order[t]
            src := sources[k]
            if p+len(src) <= len(s) && s[p:p+len(src)] == src {
                buf = append(buf, targets[k]...)
                p += len(src)
            } else {
                buf = append(buf, s[p])
                p++
            }
            t++
        } else {
            buf = append(buf, s[p])
            p++
        }
    }
    return string(buf)
}

复杂度分析

• 时间复杂度：$O(k \log k +

  s

  + \sum

  source_i

  + \sum

  target_i

  )$。排序规则下标是 $O(k \log k)$；主扫描中 $p$ 单调走遍原串是 $O(

  s

  )$，其中每次匹配判定要逐字符比较 source（总计不超过所有 source 长度之和），每次成功写入要拷贝 target。在 $

  s

  \le 1000$、$k \le 100$、单个模式串不超过 50 的约束下，总量在万级。

• 空间复杂度：$O(k +

  s

  + \sum

  target_i

  )$。$order$ 数组占 $O(k)$，输出缓冲区的长度是原串长度减去被替换掉的部分再加上所有 target 的长度。这里不能省掉缓冲区——「同时发生」的语义要求原串在整个过程中保持只读。

关键点总结

• 「同时发生」的语义等于「只读原串、只写新缓冲区」。任何在结果上就地修改的写法都会让后续规则看到前面的产物、或者让下标失准。识别出这类语义后，实现方式几乎是唯一的：单调扫描原串、拼接到别处。
• 平行数组要排序时，排的是间接下标。indexes、sources、targets 三者按位置一一对应，直接排其中之一会破坏对应关系。建一个 $order$ 数组存原下标、按关键字排它，是处理这类结构的通用手法。
• 双指针的推进步长要各自对应各自的坐标系。$p$ 走在原串上，所以匹配成功时跳的是 source 的长度；target 只影响输出缓冲区，与 $p$ 无关。混淆两个坐标系是本题最高频的错误。
• 判定失败也要消费掉这条规则。$t$ 必须无条件前进，否则一条废规则会永久卡住指针，后面所有规则都触发不了。写「判定 + 推进」型循环时，要确保每个分支都让至少一个指针前进。
• 越界检查靠短路求值前置。p + len(src) <= len(s) && 内容相等 这个顺序不是风格问题：反过来写会先截取子串而越界。凡是「先保证操作合法、再执行操作」的场景，都该用短路把守卫放在前面。
• 面试视角：这题代码不难，面试官考的是你有没有读懂「同时发生」。开口先说「所有匹配都在原串上判定、所有下标都是原串下标，所以我不修改原串，而是扫描一遍拼出新串」，基本就过关了。常见追问有三个：一是「indexes 无序怎么办」，答排序间接下标；二是「匹配失败时指针怎么走」，答只走一格但要消费掉这条规则；三是「如果题目不保证替换互不重叠呢」，正确回答是需要额外定义冲突时的优先级（比如取下标最小或规则序号最小的那条），并在跳过一段时同步跳过所有起点落在这段内的规则。能主动指出「$p$ 跳 source 长度而非 target 长度」，说明你在心里跑过一遍循环。

易错点总结

• 错误写法：按给定顺序逐条在字符串上执行替换。以 s = "abcd"、indexes = [0,2]、sources = ["a","cd"]、targets = ["eee","ffff"] 为例，第一条替换后串变成 "eeebcd"，第二条规则的下标 2 此时指向的是 'e' 而不是 'c'，匹配失败，返回 "eeebcd"，而正确答案是 "eeebffff"。所有下标都是原串下标。
• 错误写法：匹配成功后 $p$ 前进 target 的长度。以上例为例，第一条规则的 target 长度是 3，$p$ 会从 0 跳到 3，直接跳过了 'b' 和 'c'，结果变成 "eeed"。$p$ 走在原串上，消费的是 source 那么多个字符。
• 错误写法：匹配失败后 $p$ 前进 source 的长度。以 s = "abcd"、indexes = [0,2]、sources = ["ab","ec"]、targets = ["eee","ffff"] 为例，第二条规则匹配失败时若跳 2 格，字符 'd' 被吞掉，返回 "eeec"，而正确答案是 "eeecd"。不生效的规则不消费任何原文，只能一格一格走。
• 错误写法：匹配失败后不推进 $t$。以同一组数据为例，$t$ 永远停在第二条规则上；虽然后续 $p$ 与它的起始位置不再相等而落入普通分支，但如果还有第三条规则，它永远等不到 $t$ 指向自己，全部失效。每个分支都要保证指针有推进。
• 错误写法：不排序，直接按给定顺序用 $t$ 扫描规则。以 s = "abcd"、indexes = [2, 0]、sources = ["cd", "a"]、targets = ["ffff", "eee"] 为例，$p = 0$ 时 $t$ 指向的规则起始位置是 2，不相等，于是原样输出 'a'；$p = 2$ 时终于匹配上第一条，但第二条（下标 0）再也没机会触发，返回 "abffff"，而正确答案是 "eeebffff"。
• 错误写法：直接对 indexes 数组排序。以任意输入为例，排序后 indexes[i] 与 sources[i]、targets[i] 的对应关系被打乱，每条规则都会拿到别人的模式串和替换串，结果完全错乱。平行数组必须排间接下标。
• 错误写法：先截取子串再判长度。以 s = "ab"、indexes = [1]、sources = ["bcd"] 为例，从下标 1 截取 3 个字符会越界，Java 抛 StringIndexOutOfBoundsException，Go 的切片操作直接 panic。长度检查必须靠短路求值排在内容比较之前。
• 错误写法：循环条件写成 t < n。以 s = "abcd"、indexes = [0]、sources = ["a"]、targets = ["eee"] 为例，规则用尽后循环立刻退出，返回 "eee"，而正确答案是 "eeebcd"。未被规则覆盖的后缀必须继续输出，循环条件应由 $p$ 控制。
• 错误写法：从右往左倒序执行替换以规避下标失准。以某条 target 恰好在结果串中拼出另一条 source 模式的输入为例，倒序虽然保住了左侧的下标，但被修改过的右侧内容仍可能被左侧规则的匹配判定读到，违反「所有判定都基于原串」。只读原串是唯一稳妥的做法。
• 错误写法：用 indexes[order[t]] <= p 作为触发条件。以任意输入为例，这会让某条规则在它的起点被跳过之后仍然触发（比如前一条替换把 $p$ 跳过了它的起点），在本题「保证不重叠」的约束下不会发生，但一旦迁移到允许重叠的变体，就会在错误的位置插入 target。触发条件应是精确相等，跳过规则要靠显式推进 $t$。
• 错误写法：Java 里用 int[] order 配合 Arrays.sort(order, comparator)。基本类型数组的排序不接受比较器，编译不通过；必须用 Integer[]（如本代码）或改写成手动排序 / 先打包成二维数组。这是 Java 里排序自定义键的经典绊脚石。
• 错误写法：Go 里排序写成 sort.Slice(order, func(i, j int) bool { return indexes[i] < indexes[j] })。比较函数收到的 $i$、$j$ 是 $order$ 切片内部的位置，必须用 indexes[order[i]] < indexes[order[j]] 才是按规则的起始位置比较。写成 indexes[i] 排的是一个与 $order$ 内容无关的固定序列，结果不可预测。

相似题目

题目	难度	考察点
56. 合并区间	中等	同样先按起始位置排序再线性扫描，但要合并相交区间而非独立处理
28. 找出字符串中第一个匹配项的下标	简单	纯子串匹配，本题的匹配判定是它的定点版本（只需在指定下标处比一次）
443. 压缩字符串	中等	读指针与写指针分别推进的原地改写，训练「两个坐标系各自推进」的手感
71. 简化路径	中等	边扫描边决定往输出里写什么，重点在分段解析与栈的配合
68. 文本左右对齐	困难	大量边界条件的字符串拼接题，考察的是把规则逐条落实为分支的耐心
937. 重新排列日志文件	中等	自定义比较器排序并保持原有相对顺序，与本题排间接下标是同一类平行数据处理
6. Z 字形变换	中等	输出位置与原串位置的映射关系复杂，同样要求「不在原串上改，另开缓冲区拼」
763. 划分字母区间	中等	先预处理每个字符的最远位置再单调扫描切分，是「预处理 + 一次扫描」的另一形态