LeetCode 833 Find And Replace in String

LeetCode

<div>

You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the i<sup>th</sup> replacement operation:

1. Check if the substring sources[i] occurs at index indices[i] in the original string s.
2. If it does not occur, do nothing.
3. Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "<u>ab</u>cd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "<u>eee</u>cd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

• For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:

<pre>Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"] Output: "eeebffff" Explanation: "a" occurs at index 0 in s, so we replace it with "eee". "cd" occurs at index 2 in s, so we replace it with "ffff". </pre>

Example 2:

<pre>Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"] Output: "eeecd" Explanation: "ab" occurs at index 0 in s, so we replace it with "eee". "ec" does not occur at index 2 in s, so we do nothing. </pre>

Constraints:

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indexes[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s consists of only lowercase English letters.
• sources[i] and targets[i] consist of only lowercase English letters.

</div>

题目大意：

整洁题。找到位置，然后验证，最后替换

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. i是循环外的变量，所以poplate index_dict注意不能重名

Python代码：

def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
	res = ''
	index_dict = {}
	for _i, _n in enumerate(indices):
		index_dict[_n] = _i # 0 -> 0, 2 -> 1
	i = 0
	while i < len(s):
		if i in index_dict and s[i:i + len(sources[index_dict[i]])] == sources[index_dict[i]]:
			res += targets[index_dict[i]]
			i += len(sources[index_dict[i]])
		else:
			res += s[i]
			i += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)