Lintcode: String Replace

String Replace

Similar Problems:

Given two identical-sized string array A, B and a string S. All substrings A appearing in S are replaced by B.(Notice: From left to right, it must be replaced if it can be replaced. If there are multiple alternatives, replace longer priorities. After the replacement of the characters can’t be replaced again.)


  • The size of each string array does not exceed 100, the total string length does not exceed 50000.
  • The lengths of A [i] and B [i] are equal.
  • The length of S does not exceed 50000.
  • All characters are lowercase letters.
  • We guarantee that the A array does not have the same string

Given A = [“ab”,”aba”], B = [“cc”,”ccc”], S = “ababa”, return “cccba”.

In accordance with the rules, the substring that can be replaced is "ab" or "aba". Since "aba" is longer, we replace "aba" with "ccc".  

Given A = [“ab”,”aba”], B = [“cc”,”ccc”] ,S = “aaaaa” ,return “aaaaa”.

S does not contain strings in A, so no replacement is done.

Given A = [“cd”,”dab”,”ab”], B = [“cc”,”aaa”,”dd”], S = “cdab”, return “ccdd”.

From left to right, you can find the "cd" can be replaced at first, so after the replacement becomes "ccab", then you can find "ab" can be replaced, so the string after the replacement is "ccdd".


Credits To:

Leave me comments, if you have better ways to solve.

## Blog link:
class TrieNode:
    def __init__(self):
        import collections
        self.value = None
        self.children = collections.defaultdict(TrieNode)

class Solution:
    @param a: The A array
    @param b: The B array
    @param s: The S string
    @return: The answer
    def stringReplace(self, a, b, s):
        ## Basic Ideas: Trie tree
        ## Complexity: Time O(kn), Space O(m)
        ##      n = len(s), m = total string length of a
        root = TrieNode()

        # add node to TrieTree
        for i in range(len(a)):
            string = a[i]
            if string not in s: continue
            p = root
            for ch in string:
                p = p.children[ch]
            p.value = b[i]

        # search TrieTree
        res = ""
        i = 0
        while i<len(s):
            p = root
            index, string = i, None
            for j in range(i, len(s)):
                ch = s[j]
                if ch not in p.children:
                p = p.children[ch]
                # track possible result
                if p.value:
                    index, string = j, p.value

            if string is not None:
                res += string
                i = index + 1
                res += s[i]
                i += 1

        # get the result
        return res

Share It, If You Like It.

Leave a Reply

Your email address will not be published.