LeetCode: Find And Replace in String C#

Question

It took me a while to solve this question and there are corner cases i missed hence the 4 unit tests. please review for performance. and if you can treat this as a review for a 45 mins programming interview.

https://leetcode.com/problems/find-and-replace-in-string/

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.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StringQuestions
{      
    [TestClass]
    public class FindReplaceStringTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            string S = "abcd";
            int[] indexes = { 0, 2 };
            string[] sources = { "a", "cd" };
            string[] targets = { "eee", "ffff" };
            string output = "eeebffff";
            Assert.AreEqual(output, FindReplaceStringClass.FindReplaceString(S, indexes, sources, targets));
        }


        [TestMethod]
        public void TestFailMethod1()
        {
            string S = "abcd";
            int[] indexes = { 0, 2 };
            string[] sources = { "ab", "ec" };
            string[] targets = { "eee", "ffff" };
            string output = "eeecd";
            Assert.AreEqual(output, FindReplaceStringClass.FindReplaceString(S, indexes, sources, targets));

        }

        [TestMethod]
        public void TestFailMethod2()
        {
            string S = "vmokgggqzp";
            int[] indexes = { 3, 5, 1 };
            string[] sources = { "kg", "ggq", "mo" };
            string[] targets = { "s", "so", "bfr" };
            string output = "vbfrssozp";
            Assert.AreEqual(output, FindReplaceStringClass.FindReplaceString(S, indexes, sources, targets));
        }

        [TestMethod]
        public void TestFailMethod3()
        {
            string S = "jjievdtjfb";
            int[] indexes = { 4,6,1 };
            string[] sources = { "md", "tjgb", "jf" };
            string[] targets = { "foe", "oov", "e" };
            string output = "jjievdtjfb";
            Assert.AreEqual(output, FindReplaceStringClass.FindReplaceString(S, indexes, sources, targets));
        }
        
    }
}

public class FindReplaceStringClass
{
    public static string FindReplaceString(string S, int[] indexes, string[] sources, string[] targets)
    {
        var index2strings = new SortedDictionary<int, Tuple<string, string>>();
        for (int i = 0; i < indexes.Length; i++)
        {
            index2strings.Add(indexes[i], new Tuple<string, string>(sources[i], targets[i]));
        }

        StringBuilder res = new StringBuilder();
        int curr = 0;//current s pointer
        foreach (var item in index2strings)
        {
            var index = item.Key;
            var source = item.Value.Item1;
            var target = item.Value.Item2;
            //check each index if source appears in s
            for (int k = curr; k < index; k++)
            {
                res.Append(S[k]);
                curr++;
            }
            //check the entire prefix is found
            bool isFound = true;
            for (int sIndx = index, j = 0; sIndx < index + source.Length; sIndx++, j++)
            {
                if (S[sIndx] != source[j])
                {
                    isFound = false;
                    break;
                }
            }
            if (!isFound)
            {
                continue;
            }
            curr = index + source.Length;
            //append new string
            foreach (var t in target)
            {
                res.Append(t);
            }
        }
        //the rest of s
        for (int i = curr; i < S.Length; i++)
        {
            res.Append(S[i]);
        }
        return res.ToString();
    }

}

Answer 1

Instead of the old Tuple objects, you should use ValueTuple. They are more flexible and easier to read and maintain according to names and is further more elaborated and incorporated in C# as language. So your Dictionary could look like:

  var index2strings = new SortedDictionary<int, (string source, string target)>();
  for (int i = 0; i < indexes.Length; i++)
  {
    index2strings.Add(indexes[i], (sources[i], targets[i]));
  }

---

You can benefit from setting the capacity of the string builder to a large value, - maybe as:

  StringBuilder res = new StringBuilder(S.Length * 2);

---

Because KeyValuePair<K,V> provides a "decontructor", you can replace this:

  foreach (var item in index2strings)
  {
    var index = item.Key;
    var source = item.Value.Item1;
    var target = item.Value.Item2;

with this:

  foreach ((var index, (var source, var target)) in index2strings)
  {

if you use ValueTuple as suggested above.

---

This:

    for (int k = curr; k < index; k++)
    {
      res.Append(S[k]);
      curr++;
    }

can be replaced with:

    int length = index - curr;
    res.Append(S.Substring(curr, length));
    curr += length;

According to my measurements it's cheaper to add one string as a whole than a sequence of its chars.

---

Likewise can this:

    //check the entire prefix is found
    bool isFound = true;
    for (int sIndx = index, j = 0; sIndx < index + source.Length; sIndx++, j++)
    {
      if (S[sIndx] != source[j])
      {
        isFound = false;
        break;
      }
    }
    if (!isFound)
    {
      continue;
    }

be replaced with:

    if (S.Substring(index, source.Length) != source)
    {
      continue;
    }

and this:

    foreach (var t in target)
    {
      res.Append(t);
    }

with:

    res.Append(target);

and finally this:

  for (int i = curr; i < S.Length; i++)
  {
    res.Append(S[i]);
  }

with:

  res.Append(S.Substring(curr));

When doing so it seems that you can cut the duration to about a little lesser than half the time.