Step by Step solution about How to resolve the algorithm Shortest common supersequence step by step in the Java programming language

Problem Statement: Given two strings, find their shortest common supersequence (SCS).

Shortest Common Supersequence (SCS): The SCS of two strings is the shortest string that contains both strings as subsequences.

Solution Overview: This solution uses recursion to compute the SCS of two strings.

Key Variables:

• x and y: The input strings.

Recursive Function: The scs function takes two substrings x and y as input and returns the SCS of these substrings.

• Base Cases:
  • If either x or y is empty, the SCS is the other string.
• Recursive Case:
  • If the first characters of x and y match, they are prepended to the SCS of the remaining substrings.
  • Otherwise, the SCS with the shorter length is prepended with the first character of the longer string.

Main Method: The main method initializes two strings x and y and then calls the scs function to find and print their SCS.

Example: For the input strings x = "abcbdab" and y = "bdcaba", the output will be "abdcbdabca" which is the shortest common supersequence of x and y.

Time Complexity: The time complexity of this solution is exponential, as it is a recursive function that explores all possible combinations. In the worst case, it can be as high as O(2^n), where n is the length of both x and y.

Space Complexity: The space complexity of this solution is O(n), where n is the length of x and y, as it stores recursive calls on the stack.

public class ShortestCommonSuperSequence {
    private static boolean isEmpty(String s) {
        return null == s || s.isEmpty();
    }

    private static String scs(String x, String y) {
        if (isEmpty(x)) {
            return y;
        }
        if (isEmpty(y)) {
            return x;
        }

        if (x.charAt(0) == y.charAt(0)) {
            return x.charAt(0) + scs(x.substring(1), y.substring(1));
        }

        if (scs(x, y.substring(1)).length() <= scs(x.substring(1), y).length()) {
            return y.charAt(0) + scs(x, y.substring(1));
        } else {
            return x.charAt(0) + scs(x.substring(1), y);
        }
    }

    public static void main(String[] args) {
        System.out.println(scs("abcbdab", "bdcaba"));
    }
}