Print one Shortest Common Supersequence

shriyanshi24jindal

Mar 28th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 15.67 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
Start from i = n, j = m. Use a StringBuilder to store characters.
While i > 0 && j > 0:
If s1.charAt(i-1) == s2.charAt(j-1)
→ This character is part of both strings
→ append it and move diagonally (i--, j--)
Else if t[i-1][j] > t[i][j-1]
→ append s1.charAt(i-1)
→ move up (i--)
Else
→ append s2.charAt(j-1)
→ move left (j--)
If one string still has characters left:
append remaining s1
append remaining s2
Reverse the StringBuilder at the end (because we built it backwards).
*/
public String shortestCommonSupersequence(String str1, String str2) {
int n = str1.length();
int m = str2.length();
// create a matrix
int[][] t = new int[n+1][m+1];
// initialise the matrix with base condition
for(int i=0; i<n+1; i++)
{
for(int j=0; j<m+1; j++)
{
if(i == 0 || j == 0)
t[i][j] = 0;
}
}
// fill the matrix
for(int i=1; i<n+1; i++)
{
for(int j=1; j<m+1; j++)
{
if(str1.charAt(i-1) == str2.charAt(j-1))
{
t[i][j] = 1 + t[i-1][j-1];
}
else
t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
}
}
// Backtrack to construct the SCS string
int i=n;
int j=m;
String s = "";
while(i>0 && j>0)
{
if(str1.charAt(i-1) == str2.charAt(j-1))
{
s += str1.charAt(i-1);
// move diagonally
i--;
j--;
}
else
{
if(t[i-1][j] > t[i][j-1])
{
s += str1.charAt(i-1);
// move up
i--;
}
else
{
s += str2.charAt(j-1);
// move left
j--;
}
}
}
while(i>0)
{
s += str1.charAt(i-1);
i--;
}
while(j>0)
{
s += str2.charAt(j-1);
j--;
}
return new StringBuilder(s).reverse().toString();
}
}

RAW Paste Data Copied

class Solution {
    /**
    Start from i = n, j = m. Use a StringBuilder to store characters.
    While i > 0 && j > 0:
        If s1.charAt(i-1) == s2.charAt(j-1)
            → This character is part of both strings
            → append it and move diagonally (i--, j--)

Else if t[i-1][j] > t[i][j-1]
            → append s1.charAt(i-1)
            → move up (i--)

Else
            → append s2.charAt(j-1)
            → move left (j--)
    If one string still has characters left:
        append remaining s1
        append remaining s2
    Reverse the StringBuilder at the end (because we built it backwards).
    */
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();

// create a matrix
        int[][] t = new int[n+1][m+1];

// initialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

// fill the matrix
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(str1.charAt(i-1) == str2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }

// Backtrack to construct the SCS string
        int i=n;
        int j=m;
        String s = "";
        while(i>0 && j>0)
        {
            if(str1.charAt(i-1) == str2.charAt(j-1))
            {
                s += str1.charAt(i-1);
                // move diagonally
                i--;
                j--;
            }
            else
            {
                if(t[i-1][j] > t[i][j-1])
                {
                    s += str1.charAt(i-1);
                    // move up
                    i--;
                }
                else
                {
                    s += str2.charAt(j-1);
                    // move left
                    j--;
                }
            }
        }

while(i>0)
        {
            s += str1.charAt(i-1);
            i--;
        }

while(j>0)
        {
            s += str2.charAt(j-1);
            j--;
        }
        return new StringBuilder(s).reverse().toString();
    }
}