LeetCode: 833. Find And Replace in String

The very first thing to do is looking for matches.

We don't need to use any fancy algorithms when looking for matches in this problem because it is guranteed that replacements will not overlap.

 

Now we have matched list in the form of [index, source, target].

If you are planning to replace s directly, it will lead to bad time complexity as you will have to copy all the characters of s each time you replace a word. --> O(len(s) * num_replacements) ~= 1000 * 100 in this prob

 

So we use list(strList) instead. We chop the string into the list while replacing source with target at the same time. 

* matched.sort() is necessary when matched index are not in ascending order.

 

Below is the code.

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        # [index, source, target]
        matched = []
        k = len(indices)
        for i in range(k):
            idx, source, target = indices[i], sources[i], targets[i]
            # match?
            if s[idx:idx+len(source)] == source:
                matched.append((idx, source, target))
        
        matched.sort()
        strList, prv = [], 0
        for idx, source, target in matched:
            strList.append(s[prv:idx])
            strList.append(target)
            prv = idx + len(source)
        strList.append(s[prv:])
        
        return ''.join(strList)