Is Subsequence

shriyanshi24jindal

Mar 28th, 2026

Never

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

Java 10.30 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
Approach used: Dynamic Programming (Longest Common Subsequence – LCS)
The code computes the Longest Common Subsequence (LCS) between strings s and t using a DP table
dp[i][j] stores the length of LCS of the first i characters of s and first j characters of t.
If characters match (s[i-1] == t[j-1]), then dp[i][j] = 1 + dp[i-1][j-1];
otherwise take the maximum of skipping one character from either string.
After filling the table, the LCS length is dp[n][m].
If LCS length equals the length of s,
then all characters of s appear in order in t, meaning s is a subsequence of t.
*/
public boolean isSubsequence(String s, String t) {
int n = s.length();
int m = t.length();
int length = findLCS(s, t, n, m);
if(length == s.length())
return true;
return false;
}
public int findLCS(String s1, String s2, int n, int m)
{
// create a matrix
int[][] t = new int[n+1][m+1];
// initialise 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 - LCS
for(int i=1; i<n+1; i++)
{
for(int j=1; j<m+1; j++)
{
if(s1.charAt(i-1) == s2.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 {
    /**
    Approach used: Dynamic Programming (Longest Common Subsequence – LCS)
    The code computes the Longest Common Subsequence (LCS) between strings s and t using a DP table
    dp[i][j] stores the length of LCS of the first i characters of s and first j characters of t.
        If characters match (s[i-1] == t[j-1]), then dp[i][j] = 1 + dp[i-1][j-1]; 
        otherwise take the maximum of skipping one character from either string.
    After filling the table, the LCS length is dp[n][m].
    If LCS length equals the length of s, 
        then all characters of s appear in order in t, meaning s is a subsequence of t.
    */
    public boolean isSubsequence(String s, String t) {
        int n = s.length();
        int m = t.length();

int length = findLCS(s, t, n, m);

if(length == s.length())
            return true;

return false;
    }

public int findLCS(String s1, String s2, int n, int m)
    {
        // create a matrix
        int[][] t = new int[n+1][m+1];

// initialise 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 - LCS
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(s1.charAt(i-1) == s2.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];
    }
}