Algorithms for Coding Interviews in Java/

...

/

Solution: Shortest Common Supersequence

Solution: Shortest Common Supersequence

This review provides a detailed analysis of the different ways to solve the shortest common supersequence problem.

We'll cover the following...

Solution #1: Brute force

First, let’s start by looking at the brute force solution to solve this problem.

Java
class SCS
{
  public static int findSCSLengthRecursive(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 sequences have a matching character 
    if (s1.charAt(i1) == s2.charAt(i2))
      return 1 + findSCSLengthRecursive(s1, s2, i1 + 1, i2 + 1);
    //if matching character not found
    int length1 = 1 + findSCSLengthRecursive(s1, s2, i1, i2 + 1);
    int length2 = 1 + findSCSLengthRecursive(s1, s2, i1 + 1, i2);
    //return minimum of the two 
    return Math.min(length1, length2);
  }
  public static int findSCSLength(String s1, String s2) {
    return findSCSLengthRecursive(s1, s2, 0, 0);
  }
  public static void main(String args[]) 
  {
    System.out.println(findSCSLength("abcdz", "bdcf"));
    System.out.println(findSCSLength("educative", "educative.io"));
  }
};

Explanation

In this solution, we try all the superstrings one character at a time. The code does the following:

  • If the sequences have a matching ith character, the code skips one character from both the sequences and makes a recursive call for the remaining lengths (lines 11-12).

  • If the characters don’t match, the code calls the function recursively twice by skipping one character from each string (lines 14-15).

  • The code returns the minimum result of these two calls (line 17).

Time complexity

The time complexity of the above algorithm is exponential O(2n+m)O(2^{n+m}), where n and m are the lengths of the input ...