Shortest Common Supersequence - Google Top Interview Questions


Problem Statement :


Given strings a and b, return the length of the shortest string that has both a and b as subsequences.

Example 1

Input

a = "bell"

b = "yellow"

Output

7

Explanation

One possible solution is "ybellow".


Solution :



title-img



                        Solution in C++ :

int solve(string a, string b) {
    int M = a.size(), N = b.size();
    vector<int> dp1(N + 1), dp2(N + 1);
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++)
            dp1[j] =
                a[i - 1] == b[j - 1] ? dp2[j - 1] + 1 : max(max(dp2[j], dp1[j - 1]), dp2[j - 1]);
        dp2.swap(dp1);
    }
    return M + N - dp2[N];
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String a, String b) {
        int ans = 0;
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1))
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        int temp = dp[a.length()][b.length()];
        ans = temp + (a.length() - temp) + (b.length() - temp);
        return ans;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, a, b):
        return len(a) + len(b) - self.LCS(a, b)

    def LCS(self, a, b):
        m = len(a)
        n = len(b)

        # declaring the array for storing the dp values
        L = [[None] * (n + 1) for i in range(m + 1)]

        """Following steps build L[m+1][n+1] in bottom up fashion
        Note: L[i][j] contains length of LCS of X[0..i-1]
        and Y[0..j-1]"""
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 or j == 0:
                    L[i][j] = ""
                elif a[i - 1] == b[j - 1]:
                    L[i][j] = L[i - 1][j - 1] + a[i - 1]
                else:
                    if len(L[i - 1][j]) >= len(L[i][j - 1]):
                        L[i][j] = L[i - 1][j]
                    elif len(L[i - 1][j]) < len(L[i][j - 1]):
                        L[i][j] = L[i][j - 1]

        # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
        return len(L[m][n])
                    

View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →