Longest Common Subsequence

shriyanshi24jindal

Mar 28th, 2026

Never

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

Java 20.69 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/** Recursion */
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
return findLCS(text1, text2, n, m);
}
public int findLCS(String text1, String text2, int n, int m)
{
if(n == 0 || m == 0)
return 0;
// choice diagram
// if both character matches, reduce size of both strings
if(text1.charAt(n-1) == text2.charAt(m-1))
return 1 + findLCS(text1, text2, n-1, m-1);
// if both characters does not match, then reduce lenght of either of string
else
{
int choice1 = findLCS(text1, text2, n-1, m);
int choice2 = findLCS(text1, text2, n, m-1);
return Math.max(choice1, choice2);
}
}
/** Memoization */
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] t = new int[n+1][m+1];
for(int i=0; i<n+1; i++)
Arrays.fill(t[i], -1);;
return findLCS(text1, text2, n, m, t);
}
public int findLCS(String text1, String text2, int n, int m, int[][] t)
{
if(n == 0 || m == 0)
return 0;
if(t[n][m] != -1)
return t[n][m];
// choice diagram
// if both character matches, reduce size of both strings
if(text1.charAt(n-1) == text2.charAt(m-1))
{
t[n][m] = 1 + findLCS(text1, text2, n-1, m-1, t);
return t[n][m];
}
// if both characters does not match, then reduce lenght of either of string
else
{
int choice1 = findLCS(text1, text2, n-1, m, t);
int choice2 = findLCS(text1, text2, n, m-1, t);
t[n][m] = Math.max(choice1, choice2);
return t[n][m];
}
}
/** Top-down approach */
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] t = new int[n+1][m+1];
// base condition : when either of string length becomes 0
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;
}
}
for(int i=1; i<n+1; i++)
{
for(int j=1; j<m+1; j++)
{
if(text1.charAt(i-1) == text2.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] );
}
}
return t[n][m];
}
}

RAW Paste Data Copied

class Solution {

/** Recursion */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

return findLCS(text1, text2, n, m);
    }

public int findLCS(String text1, String text2, int n, int m)
    {
        if(n == 0 || m == 0)
            return 0;
        
        // choice diagram

// if both character matches, reduce size of both strings
        if(text1.charAt(n-1) == text2.charAt(m-1))
            return 1 + findLCS(text1, text2, n-1, m-1);
        
        // if both characters does not match, then reduce lenght of either of string
        else
        {
            int choice1 = findLCS(text1, text2, n-1, m);
            int choice2 = findLCS(text1, text2, n, m-1);
            return Math.max(choice1, choice2);
        }
    }
    
    /** Memoization */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

int[][] t = new int[n+1][m+1];
        for(int i=0; i<n+1; i++)
            Arrays.fill(t[i], -1);;

return findLCS(text1, text2, n, m, t);
    }

public int findLCS(String text1, String text2, int n, int m, int[][] t)
    {
        if(n == 0 || m == 0)
            return 0;

if(t[n][m] != -1)
            return t[n][m];
        
        // choice diagram

// if both character matches, reduce size of both strings
        if(text1.charAt(n-1) == text2.charAt(m-1))
        {
            t[n][m] = 1 + findLCS(text1, text2, n-1, m-1, t);
            return t[n][m];
        }
        
        // if both characters does not match, then reduce lenght of either of string
        else
        {
            int choice1 = findLCS(text1, text2, n-1, m, t);
            int choice2 = findLCS(text1, text2, n, m-1, t);
            t[n][m] = Math.max(choice1, choice2);
            return t[n][m];
        }
    }
    
    
    /** Top-down approach */
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

int[][] t = new int[n+1][m+1];

// base condition : when either of string length becomes 0
        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;
            }
        }

for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(text1.charAt(i-1) == text2.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] );
            }
        }
        return t[n][m];
    }
}