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

2024-03-12 HGNULB 约 5 分钟

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

分类

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

标签

数组 字符串 哈希表 排序

题目描述

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

题意分析

每条规则给出原字符串上的起点、源片段和目标片段。只有源片段在该起点完全匹配时才替换，否则不执行这条规则。所有替换同时发生，位置始终以原串为准，题目保证实际替换不会重叠。

解法：排序规则编号 + 扫描原串

核心思路

[!blue]

替换会改变输出长度，因此不能在已经修改的字符串上继续按原下标定位。保留原串不变，从左到右读取并另建输出缓冲区。用 order 保存规则编号，按起点排序，避免只排序起点而打乱 indexes、sources、targets 的对应关系。

p 指向原串中尚未输出的位置，t 指向下一条待处理规则。若规则起点等于 p，就在原串上检查源片段；成功则追加目标片段，并让 p 跳过源片段长度。目标长度只影响输出，不影响接下来要读取的原坐标。

匹配失败时只消费规则，不立刻推进 p，因为同一起点可能还有其他规则。若成功替换让 p 越过某条待处理规则的起点，也要消费这条旧规则；实际替换不重叠，说明它不可能再形成需要输出的有效替换。代码用“起点不大于 p”进入规则分支，再要求“起点恰等于 p 且源匹配”才执行替换，避免规则指针停在已经越过的位置。

当没有规则可处理，或下一规则起点大于 p 时，当前原字符无需替换，直接追加并令 p++。这样输出始终对应已经消费的原串前缀，每轮至少推进原串指针或规则指针，直到原串全部处理完。规则用尽后也继续复制剩余后缀。

解题步骤

1. 按起点排序规则编号。
2. 从左到右扫描原串。
3. 消费所有起点不大于当前位置的规则；只在起点相等且源片段匹配时追加目标并跳过源片段。
4. 若下一规则尚未到来或规则已用尽，原样追加当前字符并前进。
5. 原串处理完后返回缓冲区内容。

代码实现

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 == indexes[k]
                        && p + src.length() <= s.length()
                        && s.startsWith(src, p)) {
                    sb.append(targets[k]);
                    // 原串消费的是源片段长度，目标长度只影响输出。
                    p += src.length();
                }

                // 当前规则无论成功与否都已处理，继续下一条。
                t++;
            } else {
                sb.append(s.charAt(p));
                p++;
            }
        }

        return sb.toString();
    }
}

import "sort"

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 == indexes[k] && p+len(src) <= len(s) && s[p:p+len(src)] == src {
                buf = append(buf, targets[k]...)
                // 原串消费的是源片段长度，目标长度只影响输出。
                p += len(src)
            }
            // 当前规则无论成功与否都已处理，继续下一条。
            t++
        } else {
            buf = append(buf, s[p])
            p++
        }
    }
    return string(buf)
}

复杂度分析

• 时间复杂度：$O(k\log(k+1)+N+S+T)$，N 为原串长度，S 为匹配检查的源字符串总长度，T 为写入目标总长度。
• 空间复杂度：$O(k+N+T)$，规则编号和输出缓冲。

关键点总结

[!green]

• 匹配与推进都使用原串坐标。
• 成功时跳过 source 长度，不是 target 长度。
• 失败或已经越过的规则都要被消费；失败规则不应抢先消费原字符。

易错点总结

[!yellow]

• 只排序起点数组：规则的源和目标不再一一对应。
• 成功后按目标长度推进原指针：跳过或重复原文字符。
• 失败时不推进规则指针：后续规则可能再也无法触发。
• 只接受起点等于 p 的规则却不跳过旧规则：成功替换跨过一个失败规则时，会阻塞后续有效规则。
• 规则用尽就停止：丢掉原串未被替换的后缀。

相似题目

题目	难度	关联与区别
28. 找出字符串中第一个匹配项的下标	简单	先在原字符串指定位置验证源片段是否匹配，本题再执行互不影响的替换，而非只找首次出现。
648. 单词替换	中等	同样根据匹配内容替换文本，词根题按词前缀选择，本题按原下标与给定源串匹配。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2024/43665371

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！