# 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.)

Notice

• 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

Example
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".
```

Github: code.dennyzhang.com

Credits To: lintcode.com

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

```## Blog link: https://code.dennyzhang.com/string-replace
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
"""
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()

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:
break
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
else:
res += s[i]
i += 1

# get the result
return res
```

Share It, If You Like It.