LeetCode: is subsequence C#

Question

https://leetcode.com/problems/is-subsequence/

Given a string s and a string t, check if s is subsequence of t.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits: Special thanks to @pbrother for adding this problem and creating all test cases.

Example 1:

Input: s = "abc", t = "ahbgdc" Output: true Example 2:

Input: s = "axc", t = "ahbgdc" Output: false

Constraints:

0 <= s.length <= 100 0 <= t.length <= 10^4 Both strings consists only of lowercase characters.

Please review for performance.

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

namespace RecurssionQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/is-subsequence/
    /// </summary>
    [TestClass]
    public class IsSubsequenceTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            string s = "abc", t = "ahbgdc";
            Assert.IsTrue(IsSubsequence(s, t));
            Assert.IsTrue(IsSubsequence2(s, t));
        }

        [TestMethod]
        public void TestMethod2()
        {
            string s = "axc", t = "ahbgdc";
            Assert.IsFalse(IsSubsequence(s, t));
            Assert.IsFalse(IsSubsequence2(s, t));
        }



        public bool IsSubsequence(string s, string t)
        {
            return Helper(s, t, 0, 0);
        }

        /// <summary>
        /// if the letters are equal (letter is found) continue to the next letter of s
        /// if the letter is not found in t continue to the next letter of t.
        /// if you reached the end of s, then s is a subsequence  of t.
        /// if you reach the end of t. then s is not a subsequence of t
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <param name="sIndex"></param>
        /// <param name="tIndex"></param>
        /// <returns></returns>
        private bool Helper(string s, string t, int sIndex, int tIndex)
        {
            if (sIndex == s.Length)
            {
                return true;
            }
            if (tIndex == t.Length)
            {
                return false;
            }
            if (s[sIndex] == t[tIndex])
            {
                return Helper(s, t, sIndex + 1, tIndex + 1);
            }
            else
            {
                return Helper(s, t, sIndex, tIndex + 1);
            }
        }

        public bool IsSubsequence2(string s, string t)
        {
            if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))
            {
                return false;
            }

            Dictionary<char, List<int>> map = new Dictionary<char, List<int>>();

            //pre-process t
            for (int i = 0; i < t.Length; i++)
            {
                if (!map.ContainsKey(t[i]))
                {
                    map.Add(t[i], new List<int>());
                }

                map[t[i]].Add(i);
            }

            int prev = -1;
            for (int i = 0; i < s.Length; i++)
            {
                if (!map.ContainsKey(s[i]))
                {
                    return false;
                }
                else
                {
                    var list = map[s[i]];
                    prev = BinarySearch(prev, list, 0, list.Count - 1);
                    if (prev == -1)
                    {
                        return false;
                    }

                    prev++;
                }
            }

            return true;
        }


        private int BinarySearch(int prev, List<int> list, int start, int end)
        {
            while (start <= end)
            {
                int mid = (end - start) / 2 + start;
                if (list[mid] < prev)
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }

            if (start == list.Count)
            {
                return -1;
            }

            return list[start];
        }
    }
}

Answer 1

From a performance point of perspective, IsSubsequence will always be faster than IsSubsequence2, because it only needs to iterate 2 arrays simultaneously and has no further allocations on the heap.

If you want to improve on performance and also make sure, you never get a StackOverFlowException, you should get rid of the recursion in your Helper method and instead use a loop.

public static bool IsSubsequence3(string s, string t)
{
    var sIndex = 0;
    for (var tIndex = 0; tIndex < t.Length; tIndex++)
    {
        if (s[sIndex] == t[tIndex])
            sIndex++;
    
        if(sIndex == s.Length)
            return true;
    }
    
    return false;
}

When running a Debug build, using the input string s = "abc", t = "ahbgdc"; and executing the Method more than 1,000,000 times, IsSubsequence4 becomes faster. However when you run it in a Release build, the performance is the same, as compiler optimizations kick in and they will implicitly do what is written here explicitly (trade the property access for a local field).

public static bool IsSubsequence4(string s, string t)
{
    var sIndex = 0;
    var sLength = s.Length;
    var tLength = t.Length;
    for (var tIndex = 0; tIndex < tLength; tIndex++)
    {
        if (s[sIndex] == t[tIndex])
            sIndex++;
    
        if(sIndex == sLength)
            return true;
    }
    
    return false;
}

I also tried using AsSpan() and ToCharArray() and the strings to get rid of the callvirt System.String.get_Chars in the IL code and I tried using an Enumerator. Both where slower than IsSubsequence3

public static bool IsSubsequence5(string s, string t)
{
    var sIndex = 0;
    var sLength = s.Length;
    var tLength = t.Length;
    var sChars = s.AsSpan();
    var tChars = t.AsSpan();
    for (var tIndex = 0; tIndex < tLength; tIndex++)
    {
        if (sChars[sIndex] == tChars[tIndex])
            sIndex++;
    
        if(sIndex == sLength)
            return true;
    }
    
    return false;
}

public static bool IsSubsequence6(string s, string t)
{
    using var sEnum = s.GetEnumerator();
    sEnum.MoveNext();
    using var tEnum = t.GetEnumerator();
    while (tEnum.MoveNext())
    {
        if (sEnum.Current == tEnum.Current)
        {
            if(!sEnum.MoveNext())
                return true;
        }
    }
    
    return false;
}