C# Solution

  • 0

    Originally attempted a simple recursion but failed during the many a and b input strings, where I decided to take a more constructive approach. I use a tuple to track the indices of s1 and s2 maintaining a list of valid indices until there are no more candidates or s3 has been fully iterated. Everything in valid indices is valid up to but not including the index listed. e.g. 0,0 the seed is vacuously true for every string.

    public class Solution {
        public bool IsInterleave(string s1, string s2, string s3) {
            if(s3.Length != s1.Length + s2.Length)
                return false;
            // use a hashset to avoid unecessary bifurcation
            HashSet<Tuple<int, int>> validIndices = new HashSet<Tuple<int, int>>() { new Tuple<int, int>(0, 0) };
            int s3Index = 0;
            while(validIndices.Any() && s3Index < s3.Length) {
                HashSet<Tuple<int, int>> nextRoundIndices = new HashSet<Tuple<int, int>>();
                foreach(var index in validIndices) {
                    if(index.Item1 < s1.Length && s3[s3Index] == s1[index.Item1])
                        nextRoundIndices.Add(new Tuple<int, int>(index.Item1 + 1, index.Item2));
                    if (index.Item2 < s2.Length && s3[s3Index] == s2[index.Item2])
                        nextRoundIndices.Add(new Tuple<int, int>(index.Item1, index.Item2 + 1));
                validIndices = nextRoundIndices;
            return validIndices.Any() && s3Index == s3.Length;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.