833_Find and Replace in String

[Medium]

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

Each replacement operation has3parameters: a starting indexi, a source word x and a target word y. The rule is that ifx starts at positioni in the original stringS, 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 position2 in the original stringS, we will replace it with"ffff".

Using another example onS = "abcd", if we have both the replacement operationi = 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.

Notes:

1. 0<= indexes.length = sources.length = targets.length<= 100

2. 0<indexes[i]<S.length<= 1000

3. All characters in given inputs are lowercase letters.

Solution

Idea:

• Zip indexes, sources and targets, and sort then by descending order on indexes

• Loop form the largest indexes, check if the replacing condition satisfies, if so, replace using array assignment.

• Must start from the right, because otherwise, the index of the original S will be changed after on replacement.

• S[i:j] = A is doable for list A which may have different size of S[i:j] as long as we use slicing as S[i:j] not only use S.

def findReplaceString(S, indexes, sources, targets):
    """
    :type S: str
    :type indexes: List[int]
    :type sources: List[str]
    :type targets: List[str]
    :rtype: str
    """
    S = list(S)

    # loop backwards
    for i, x, y in sorted(zip(indexes, sources, targets), reverse = True):
        if all(i+k < len(S) and S[i+k] == x[k] for k in range(len(x))):
            S[i:i+len(x)] = list(y)

    return "".join(S)