Print All LCS

shriyanshi24jindal

Mar 28th, 2026

Never

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

Java 30.78 KB | None | 0 0

copy raw download clone embed print report

// User function Template for Java
class Node
{
int i;
int j;
String str;
Node(int i, int j, String str)
{
this.i = i;
this.j = j;
this.str = str;
}
}
class Solution {
// TreeSet automatically keeps elements sorted lexicographically.
Set<String> set = new TreeSet<>();
/** Memoization **/
public List<String> allLCS(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// step-1 create a matrix
int[][] t = new int[n+1][m+1];
// step-2 initialise the matrix acc. to base condition
for(int i=0; i<n+1; i++)
{
for(int j=0; j<m+1; j++)
{
// Base case: If either string is empty, LCS is 0.
if(i == 0 || j == 0)
t[i][j] = 0;
}
}
// step-3 convert recursive code to iterative
for(int i=1; i<n+1; i++)
{
for(int j=1; j<m+1; j++)
{
// If the current characters match, add 1 to the previous LCS length.
if(s1.charAt(i-1) == s2.charAt(j-1))
{
t[i][j] = 1 + t[i-1][j-1];
}
// If the current characters do not match, take the maximum of the LCS
// when one character from either string is excluded.
else
t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
}
}
// print all LCS
printAllLCS(s1, s2, n, m, t, "");
List<String> list = new ArrayList<>();
list.addAll(set);
return list;
}
public void printAllLCS(String s1, String s2, int i, int j, int[][] t, String str)
{
if(i == 0 || j == 0)
{
set.add(new StringBuilder(str).reverse().toString());
return;
}
if(s1.charAt(i-1) == s2.charAt(j-1))
{
printAllLCS(s1, s2, i-1, j-1, t, str + s1.charAt(i-1));
}
else
{
// If both equal → explore both paths (this creates multiple LCS).
if(t[i-1][j] >= t[i][j-1])
printAllLCS(s1, s2, i-1, j, t, str);
if(t[i][j-1] >= t[i-1][j])
printAllLCS(s1, s2, i, j-1, t, str);
}
}
/** Top-Down Approach **/
public List<String> allLCS(String s1, String s2) {
int n = s1.length();
int m = s2.length();
// step-1 create a matrix
int[][] t = new int[n+1][m+1];
// step-2 initialise the matrix acc. to base condition
for(int i=0; i<n+1; i++)
{
for(int j=0; j<m+1; j++)
{
// Base case: If either string is empty, LCS is 0.
if(i == 0 || j == 0)
t[i][j] = 0;
}
}
// step-3 convert recursive code to iterative
for(int i=1; i<n+1; i++)
{
for(int j=1; j<m+1; j++)
{
// If the current characters match, add 1 to the previous LCS length.
if(s1.charAt(i-1) == s2.charAt(j-1))
{
t[i][j] = 1 + t[i-1][j-1];
}
// If the current characters do not match, take the maximum of the LCS
// when one character from either string is excluded.
else
t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
}
}
Stack<Node> st = new Stack<>();
st.push(new Node(n, m, ""));
while(!st.isEmpty())
{
Node curr = st.pop();
int i = curr.i;
int j = curr.j;
String s = curr.str;
if(i == 0 || j == 0)
{
set.add(new StringBuilder(s).reverse().toString());
continue;
}
if(s1.charAt(i-1) == s2.charAt(j-1))
st.push(new Node(i-1, j-1, s + s1.charAt(i-1)));
else
{
// explore both paths
if(t[i-1][j] >= t[i][j])
st.push(new Node(i-1, j, s));
if(t[i][j-1] >= t[i][j])
st.push(new Node(i, j-1, s));
}
}
List<String> list = new ArrayList<>();
list.addAll(set);
return list;
}
}

RAW Paste Data Copied

// User function Template for Java
class Node
{
    int i;
    int j;
    String str;
    
    Node(int i, int j, String str)
    {
        this.i = i;
        this.j = j;
        this.str = str;
    }
}

class Solution {
    // TreeSet automatically keeps elements sorted lexicographically.
    Set<String> set = new TreeSet<>();
    
    /** Memoization **/
    public List<String> allLCS(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];
        
        // step-2 initialise the matrix acc. to base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                // Base case: If either string is empty, LCS is 0.
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }
        
        // step-3 convert recursive code to iterative
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                // If the current characters match, add 1 to the previous LCS length.
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                // If the current characters do not match, take the maximum of the LCS
                // when one character from either string is excluded.
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }
        
        // print all LCS
        printAllLCS(s1, s2, n, m, t, "");
        List<String> list = new ArrayList<>();
        list.addAll(set);
        return list;
    }
    
    public void printAllLCS(String s1, String s2, int i, int j, int[][] t, String str)
    {
        if(i == 0 || j == 0)
        {
            set.add(new StringBuilder(str).reverse().toString());
            return;
        }
        
        if(s1.charAt(i-1) == s2.charAt(j-1))
        {
            printAllLCS(s1, s2, i-1, j-1, t, str + s1.charAt(i-1));
        }
        else
        {
            // If both equal → explore both paths (this creates multiple LCS).
            if(t[i-1][j] >= t[i][j-1])
                printAllLCS(s1, s2, i-1, j, t, str);
                
            if(t[i][j-1] >= t[i-1][j])
                printAllLCS(s1, s2, i, j-1, t, str);
        }
    }
    
    /** Top-Down Approach **/
    public List<String> allLCS(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        // step-1 create a matrix
        int[][] t = new int[n+1][m+1];
        
        // step-2 initialise the matrix acc. to base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                // Base case: If either string is empty, LCS is 0.
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }
        
        // step-3 convert recursive code to iterative
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                // If the current characters match, add 1 to the previous LCS length.
                if(s1.charAt(i-1) == s2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                // If the current characters do not match, take the maximum of the LCS
                // when one character from either string is excluded.
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }
 
        Stack<Node> st = new Stack<>();
        st.push(new Node(n, m, ""));
        
        while(!st.isEmpty())
        {
            Node curr = st.pop();
            int i = curr.i;
            int j = curr.j;
            String s = curr.str;
            
            if(i == 0 || j == 0)
            {
                set.add(new StringBuilder(s).reverse().toString());
                continue;
            }
            
            if(s1.charAt(i-1) == s2.charAt(j-1))
                st.push(new Node(i-1, j-1, s + s1.charAt(i-1)));
                
            else
            {
                // explore both paths
                if(t[i-1][j] >= t[i][j])
                    st.push(new Node(i-1, j, s));
                    
                if(t[i][j-1] >= t[i][j])
                    st.push(new Node(i, j-1, s));
            }
        }
        List<String> list = new ArrayList<>();
        list.addAll(set);
        return list;
    }
}