[Google Question][LeetCode] Find And Replace in String

Problem: 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:

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

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.

Approach: Basically we just can't apply replacement whenever we have a match as it will disturb the original indexes of input string and because of that we might miss further replacement / matches. That means we first need to mark the valid replacements. We can have a hash table with key as index (staring index) where we need to make replacement and value as source and target string. 

If we look closely we can just string the indexes of source and replacement string in the sources and targets array which are same and also instead of hash table we can just have integer array of length of S as we just need to mark that at this index we need to replace the num characters where num is the length of ith source string with ith target string where 0 <= i < length of sources/targets. Basically we can just put "i" at a marker index where we get the match.

That's all!

 

Implementation in C#:

        public static string FindReplaceString(string S, int[] indexes, string[] sources, string[] targets)

        {

            int[] marker = new int[S.Length];

            Array.Fill(marker, -1);

            for (int i = 0; i < indexes.Length; ++i)

            {

                int subStrStartIndex = indexes[i];

                int subStrLength = sources[i].Length;

                if (S.Substring(subStrStartIndex, subStrLength) == sources[i])

                {

                    marker[subStrStartIndex] = i;

                }

            }

            StringBuilder result = new StringBuilder();

            int index = 0;

            while (index < S.Length)

            {

                if (marker[index] >= 0)

                {

                    result.Append(targets[marker[index]]);

                    index += sources[marker[index]].Length;

                }

                else

                {

                    result.Append(S[index++]);

                }

            }

            return result.ToString();

        }

Complexity: O(n*maxLenOfSource + m) where n is the number of sources, m length of S.