MediumNo. 0833
Find And Replace in String — LeetCode 833 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, String, Sorting
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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".
Python solution
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)Complexity
- Time
- O(L)
- Space · auxiliary
- O(n)where L is the sum of the lengths of all strings, and n is the length of the string s
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 833. Find And Replace in String is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0049 | Group Anagrams | Medium |
| 0522 | Longest Uncommon Subsequence II | Medium |
| 0692 | Top K Frequent Words | Medium |
| 0720 | Longest Word in Dictionary | Medium |
| 0721 | Accounts Merge | Medium |
| 0792 | Number of Matching Subsequences | Medium |
Frequently asked questions
- How hard is LeetCode 833. Find And Replace in String?
LeetCode 833. Find And Replace in String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 833. Find And Replace in String?
The Python solution on this page runs in O(L).
- What is the space complexity of LeetCode 833. Find And Replace in String?
The Python solution on this page uses O(n), where L is the sum of the lengths of all strings, and n is the length of the string s auxiliary space.
- What topics does LeetCode 833. Find And Replace in String cover?
LeetCode 833. Find And Replace in String is tagged Array, Hash Table, String and Sorting on LeetCode.