Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Interleaving Strings

Explore solutions to the interleaving strings problem using dynamic programming techniques. Learn how to implement brute force and tabularization approaches to efficiently determine if one string interleaves two others, understanding their time and space complexities.

We'll cover the following...

Solution 1: Brute force

C# 9.0
using System;
class Program
{
    /// <summary>
    /// Determines if the third string is an interleaving of the first two strings.
    /// </summary>
    /// <param name="m">First string.</param>
    /// <param name="n">Second string.</param>
    /// <param name="p">Third string to check for interleaving.</param>
    /// <param name="mIndex">Index in the first string.</param>
    /// <param name="nIndex">Index in the second string.</param>
    /// <param name="pIndex">Index in the third string.</param>
    /// <returns>True if the third string is an interleaving of the first two strings, otherwise False.</returns>
    public static bool FindStringsInterleavingRecursive(string m, string n, string p, int mIndex, int nIndex, int pIndex)
    {
        // If we have reached the end of all the strings
        if (mIndex == m.Length && nIndex == n.Length && pIndex == p.Length)
            return true;
        // If we have reached the end of 'p' but 'm' or 'n' still has some characters left
        if (pIndex == p.Length)
            return false;
        bool b1 = false;
        bool b2 = false;
        if (mIndex < m.Length && m[mIndex] == p[pIndex])
        {
            b1 = FindStringsInterleavingRecursive(m, n, p, mIndex + 1, nIndex, pIndex + 1);
        }
        if (nIndex < n.Length && n[nIndex] == p[pIndex])
        {
            b2 = FindStringsInterleavingRecursive(m, n, p, mIndex, nIndex + 1, pIndex + 1);
        }
        return b1 || b2;
    }
    /// <summary>
    /// Determines if the third string is an interleaving of the first two strings.
    /// </summary>
    /// <param name="m">First string.</param>
    /// <param name="n">Second string.</param>
    /// <param name="p">Third string to check for interleaving.</param>
    /// <returns>True if the third string is an interleaving of the first two strings, otherwise False.</returns>
    public static bool FindStringsInterleaving(string m, string n, string p)
    {
        return FindStringsInterleavingRecursive(m, n, p, 0, 0, 0);
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        Console.WriteLine(FindStringsInterleaving("abd", "cef", "adcbef"));
        Console.WriteLine(FindStringsInterleaving("abc", "def", "abdccf"));
        Console.WriteLine(FindStringsInterleaving("abcdef", "mnop", "mnaobcdepf"));
    }
}

Explanation

The problem follows the longest common subsequence pattern.

A basic brute force solution is to try matching m and n with p one letter at a time. Let’s assume mIndex, nIndex, and pIndex represent the current indexes of m, n, and p strings, respectively. Therefore, we have two options at any step:

  • If the letter at mIndex matches the letter at pIndex, we can recursively match for the remaining lengths of m and p.
  • If the letter at nIndex matches the letter at pIndex, we can recursively match for the remaining lengths of n and p.

Time complexity

The time complexity of the above algorithm is exponential O(2m+n ...