LeetCode 833. Find And Replace in String

Description

https://leetcode.com/problems/find-and-replace-in-string/

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn’t match x[0] = 'e'.

All these operations occur simultaneously.  It’s guaranteed that there won’t be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" starts at index 0 in S, so it's replaced by "eee".
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Constraints:

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

Explanation

From the s backwards to do the replacements.

Python Solution

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:

        for indice, source, target in sorted(zip(indices, sources, targets), reverse=True):        
            if s[indice : indice + len(source)] == source:
                s = s[:indice] + target + s[indice + len(source):]  
            else:
                s = s
                
        
        return s
                

• Time Complexity: ~NQ, where N is the length of S, and Q replacement operations.
• Space Complexity: ~N.