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.

Notes:

0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
All characters in given inputs are lowercase letters.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        l = []
        for i, tgt, rpl in zip(indexes, sources, targets):
            if s[i:i + len(tgt)] == tgt:
                l.append((i, tgt, rpl))
        l.sort()
        j = 0
        s = list(s)
        for i, tgt, rpl in l:
            s[i + j:i + j + len(tgt)] = rpl
            j += len(rpl) - len(tgt)
        return ''.join(s)

# [google ][Jenny_write 20201003 1:32 am ]

# [Jenny_write]1016. Binary String With Substrings Representing 1 To N 
# [Jenny_write]114. Longest Common Prefix
# [Jenny_write]len(A) - len(set(A)) >= 1 


class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        sources_dict = {}
        targets_dict ={}

        for i, pos_index in enumerate(indexes):
            sources_dict[pos_index] = sources[i]
            targets_dict[pos_index] = targets[i]

        # 此处一定要先建字典，再倒排序
        indexes.sort(reverse=True)

        for pos_index in indexes:
            source = sources_dict[pos_index]
            target = targets_dict[pos_index]
            tmp_str = S[pos_index:(pos_index + len(source))]
            if tmp_str == source:
                S = S[:pos_index] +target +S[pos_index+len(source):]
        return (S)



class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        for i, s, t in sorted(zip(indexes, sources, targets), reverse=True):
            if S[i:i + len(s)] == s:
                S = S[:i] + t + S[i + len(s):]
        return S

class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        result, offset = S, 0
        for i, s, t in sorted(zip(indexes, sources, targets)):
            if S[i:i+len(s)]==s:
                result = result[:offset + i] + t + result[offset + i + len(s):]
                offset += len(t) - len(s)
        return result


# [google ][Jenny_write 20201003 1:32 am ]

# [Jenny_write]1016. Binary String With Substrings Representing 1 To N 
# [Jenny_write]14. Longest Common Prefix
# [Jenny_write]

# 20201003 3:31 pm -3:39 pm 

class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        
        
        
        # Step 1: dict
        s_dict = {}
        t_dict = {}
        for i, index in enumerate(indexes):
            s_dict[index] = sources[i]
            t_dict[index] = targets[i]
        
    
        # Step 2 : revs_sort
        indexes.sort(reverse = True)
                
        # Step 3 : if 
        
        for index in indexes:
            sour  = s_dict[index]
            targ  = t_dict[index]
            le_s = len(sour)
            tmp_str = S[index:(index+le_s)] 
            
            if tmp_str == sour:
                # if true, replce
                S = S[:index]+targ + S[index+le_s:]
        return S
        
        


class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        S = list(S)
        for i, s, t in sorted(zip(indexes,sources,targets),reverse=True):
            appl = all([(i + ind < len(S)) and (S[i+ind] == s[ind]) for ind in range(len(s))])
            if appl:
                S[i:i+len(s)] = list(t)
        return ''.join(S)
        


class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        index_position = dict()
        r_list = []
        
        for pos, index in enumerate(indexes):
            source_len = len(sources[pos])
            if S[index:index + source_len] == sources[pos]:
                index_position[index] = pos
        
        next_index = 0
        for i in range(len(S)):
            if i < next_index:
                continue
            if i in index_position:
                pos = index_position[i]
                r_list.append(targets[pos])
                next_index += len(sources[pos])
            else:
                r_list.append(S[i])
                next_index += 1
                
        return ''.join(r_list)

class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        idx_og = 0
        idx_res = 0
        res = S
        for index, source, target in sorted(zip(indexes, sources, targets)):
            if S[index:index + len(source)] == source:
                index2 = index - idx_og + idx_res
                res = res[:index2] + target + res[index2 + len(source):]
                idx_og = index + len(source)
                idx_res = index2 + len(target)
        return res


class Solution:
    def check_source(self, start_idx, s, source):
        i = 0
        while i < len(source):
            if start_idx  == len(s):
                return False
        
            if source[i] != s[start_idx]:
                return False
            
            start_idx += 1
            i += 1
            
        return True
    
    def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        res = []
        i = 0
        while i < len(s):
            if i in indexes:
                idx = indexes.index(i)
                source = sources[idx]
                target = targets[idx]
                if self.check_source(i, s, source):
                    i += len(source)
                    res.append(target)
                    continue
            
            res.append(s[i])
            i += 1
        return ''.join(res)