What is the time complexity of the Find And Replace in String problem?

The time complexity is O(k * m), where k is the number of operations, and m is the average length of the source strings.

How can I optimize the replacement process for Find And Replace in String?

Optimizing string modifications by avoiding repeated string concatenations and using a new string instead of modifying in place can greatly improve performance.

What if a source does not match the substring in the string?

If the source string does not match the substring at the given index, the replacement does not occur, and the string remains unchanged for that operation.

How do array scanning and hash lookups apply to this problem?

Array scanning helps iterate through indices, and hash lookups can be used for efficiently checking and replacing substrings in the main string.

What are common edge cases in the Find And Replace in String problem?

Edge cases include situations where no replacements occur, where the source does not match at a given index, and handling out-of-bounds indices.

#833

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

字符串中的查找与替换

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出： indices , sources , targets 。要完成第 i 个替换操作: 检查子字符串 sources[i] 是否出现在原字符串 s 的索引 indices[…

数组哈希表字符串排序

题目描述

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。

要完成第 i 个替换操作:

检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
如果没有出现， 什么也不做 。
如果出现，则用 targets[i] 替换该子字符串。

例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。

所有替换操作必须同时发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。

例如，一个 s = "abc" ， indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 和 "bc" 替换重叠。

在对 s 执行所有替换操作后返回 结果字符串 。

子字符串 是字符串中连续的字符序列。

示例 1：

输入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
输出："eeebffff"
解释：
"a" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"cd" 从 s 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：s = "abcd", indices = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
输出："eeecd"
解释：
"ab" 从 s 中的索引 0 开始，所以它被替换为 "eee"。
"ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

提示：

1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indices[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s 仅由小写英文字母组成
sources[i] 和 targets[i] 仅由小写英文字母组成

lightbulb

解题思路

方法一：模拟

我们遍历每个替换操作，对于当前第 $k$ 个替换操作 $(i, \text{src})$ ，如果 $s[i..i+|\text{src}|-1]$ 与 $\text{src}$ 相等，此时我们记录下标 $i$ 处需要替换的是 $\text{targets}$ 的第 $k$ 个字符串，否则不需要替换。

接下来，我们只需要遍历原字符串 $s$ ，根据记录的信息进行替换即可。

时间复杂度 $O(L)$ ，空间复杂度 $O(n)$ 。其中 $L$ 是所有字符串的长度之和，而 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def findReplaceString(
        self, s: str, indices: List[int], sources: List[str], targets: List[str]
    ) -> str:
        n = len(s)
        d = [-1] * n
        for k, (i, src) in enumerate(zip(indices, sources)):
            if s.startswith(src, i):
                d[i] = k
        ans = []
        i = 0
        while i < n:
            if ~d[i]:
                ans.append(targets[d[i]])
                i += len(sources[d[i]])
            else:
                ans.append(s[i])
                i += 1
        return "".join(ans)

speed

复杂度分析

指标	值
时间	complexity: O(k * m), where k is the number of replacement operations and m is the average length of the source strings. This comes from checking each source string for a match at the given index. Space complexity: O(n), where n is the length of the string s, as we create a new string after performing all replacements.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of how to apply array scanning and hash lookup techniques for string modifications.
question_mark
Assess how well the candidate handles edge cases where no replacements occur or where an index does not match.
question_mark
Check for knowledge of optimizing string modifications, avoiding repeated concatenation within loops.

warning

常见陷阱

外企场景

error
Not checking if the source matches the substring before applying the replacement.
error
Modifying the string in place in an inefficient way, leading to unnecessary overhead.
error
Failing to handle cases where the source does not match the substring at a given index.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Using a hash map for faster lookups when there are many replacement operations.
arrow_right_alt
Implementing the function with a greedy approach where you prioritize larger replacements first.
arrow_right_alt
Performing all replacements in one pass through the string using a more advanced string manipulation algorithm.

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #893 特殊等价字符串组 #721 账户合并