Space
Open
From Fieldwork
Scales
Archive
We make a lookup table that's essentially a set of instructions for our "read pointer."
We store a specific tuple (length_of_source, target) at indices in order to control the flow of the read pointer i.
As we iterate through the original string s (from 0 to len(s)), we need to ask at every single step: "Do I behave normally here, or do I do something special?"
The hash map (dictionary) allows us to answer that question in O(1) (instant) time. Without it, we'd have to scan the indices array constantly.
Since we are not mutating the string in place, we effectively "delete" the old substring by simply ignoring it.
If we find a match at index i, we need to know exactly how many characters to "jump" over so we don't accidentally copy parts of the old string we intended to replace.
class Solution:
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
# Map to store valid replacements: index -> (length_of_source, targets)
lookup = {}
# 1) Validation Phase
# We zip them to handle the parallel arrays easily
for index, source, target in zip(indices, sources, targets):
# Check if the substring in s matches the source
# We use slicing to safely check bounds automatically
if s[index : index + len(source)] == source:
lookup[index] = (len(source), target)
# 2) Construction Phase
result = []
i = 0
while i < len(s):
if i in lookup:
# Found a replacement!
source_len, target_str = lookup[i]
result.append(target_str)
i += source_len # Skip past the source characters
else:
# No replacement here, keep original character
result.append(s[i])
i += 1
return ''.join(result)This approach relies on Gap Filling.
Instead of iterating through every character of the string s, we iterate through the sorted operations. We trust that between any two valid operations, the characters remain exactly the same.
Here is the mental shift:
Sort: We align the operations from left to right.
Fill Gaps: Instead of stepping $i$ by 1, we simply copy everything between the end of the last valid replacement and the start of the current one.
Replace (if valid): If the check passes, append the target and update our "last position" pointer.
class Solution:
def findReplaceString(self, s, indices, sources, targets):
# 1. Sort all operations by index
# We zip them to keep the data together, then sort based on the first item (index)
sorted_ops = sorted(zip(indices, sources, targets))
result = []
last_pos = 0
for index, source, target in sorted_ops:
# 2. Validation: Check if the source matches
if s[index : index + len(source)] == source:
# A. GAP FILL: Copy everything from the last position up to this index
# This handles the "normal" characters in one go
result.append(s[last_pos : index])
# B. REPLACE: Append the target
result.append(target)
# C. UPDATE POINTER: Move past the replaced part
last_pos = index + len(source)
# 3. Clean up: Append whatever is left after the final operation
result.append(s[last_pos:])
return "".join(result)Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode