Algorithms for Coding Interviews in C#/

...

/

Solution: Shortest Common Supersequence (SCS)

Solution: Shortest Common Supersequence (SCS)

Explore various approaches to solving the shortest common supersequence problem in detail.

We'll cover the following...

Solution 1: Brute force

using System;
class Program
{
    /// <summary>
    /// Finds the length of the shortest common supersequence.
    /// </summary>
    /// <param name="s1">First string.</param>
    /// <param name="s2">Second string.</param>
    /// <param name="i1">Starting index of substring.</param>
    /// <param name="i2">Ending index of substring.</param>
    /// <returns>Length of shortest common supersequence.</returns>
    static int ShortestCommonSupersequenceRecursive(string s1, string s2, int i1, int i2)
    {
        if (i1 == s1.Length)
            return s2.Length - i2;
        if (i2 == s2.Length)
            return s1.Length - i1;
        if (s1[i1] == s2[i2])
            return 1 + ShortestCommonSupersequenceRecursive(s1, s2, i1 + 1, i2 + 1);
        
        int length1 = 1 + ShortestCommonSupersequenceRecursive(s1, s2, i1, i2 + 1);
        int length2 = 1 + ShortestCommonSupersequenceRecursive(s1, s2, i1 + 1, i2);
        return Math.Min(length1, length2);
    }
    /// <summary>
    /// Finds the length of the shortest common supersequence.
    /// </summary>
    /// <param name="s1">First string.</param>
    /// <param name="s2">Second string.</param>
    /// <returns>Length of shortest common supersequence.</returns>
    public static int ShortestCommonSupersequence(string s1, string s2)
    {
        return ShortestCommonSupersequenceRecursive(s1, s2, 0, 0);
    }
    // Driver code to test the above method
    public static void Main()
    {
        Console.WriteLine(ShortestCommonSupersequence("abcdz", "bdcf"));
        Console.WriteLine(ShortestCommonSupersequence("educative", "educative.io"));
    }
}

Explanation

In this solution, we try all the superstrings—one character at a time.

  • If the sequences have a matching i-th character, we skip one character from both the sequences and make a recursive call for the remaining lengths (lines 20–21).
  • If the characters don’t match, we call the function recursively twice by skipping one character from each string (lines 23–24).
  • We return the minimum result of these two calls (line 26).

Time complexity

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