In this post, we are going to discuss leetcode 833 — Find And Replace in String, which is recently asked in Google, and Microsoft interviews.
Problem Analysis
You are given a 0-indexed string
s
that you must performk
replacement operations on. The replacement operations are given as three 0-indexed parallel arrays,indices
,sources
, andtargets
, all of lengthk
.To complete the replacement operation:
1. Check if the substring
sources[i]
occurs at indexindices[i]
in the original strings
.2. If it does not occur, do nothing.
3. Otherwise if it does occur, replace that substring with
targets[i]
.For example, if
s = "abcd"
,indices[i] = 0
,sources[i] = "ab"
, andtargets[i] = "eee"
, then the result of this replacement will be"eeecd"
.All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.
For example, a testcase with
s = "abc"
,indices = [0, 1]
, andsources = ["ab","bc"]
will not be generated because the"ab"
and"bc"
replacements overlap.Return the resulting string after performing all replacement operations on
s
.A substring is a contiguous sequence of characters in a string.