Search⌘ K
Home/
Courses/
Algorithms for Coding Interviews in C++

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

C++
#include <iostream>
#include <string>
using namespace std;
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 (s1[i1] == s2[i2])
    return 1 + findSCSLengthRecursive(s1, s2, i1 + 1, i2 + 1);
  int length1 = 1 + findSCSLengthRecursive(s1, s2, i1, i2 + 1);
  int length2 = 1 + findSCSLengthRecursive(s1, s2, i1 + 1, i2);
  return min(length1, length2);
}
int findSCSLength(string s1, string s2) {
  return findSCSLengthRecursive(s1, s2, 0, 0);
}
int main() {
  cout << findSCSLength("abcdz", "bdcf") << endl;
  cout << findSCSLength("educative", "educative.io") << endl;
}

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

Pseudocode

IF the sequences have a matching character
skip one character from both the sequences and make a recursive call for the remaining lengths.
IF the characters don’t match
we call the function recursively twice by skipping one character from each string. We return the minimum result of these two calls.

Time Complexity

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