Dynamic Programming 10

Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.

Problem link :- click here

Code

import java.util.Arrays;
import java.util.Scanner;

public class DynamicProgramming_10
{
	//Brute Force
	static int longestCommonSubsequence(String str1, String str2)
	{
		int n1 = str1.length();
		int n2 = str2.length();
		
		int max = 0;
		for(int k=0; k<n1; k++)
		{
			int cur = 0;
			int index = 0;
			//to store the index from which we have to start searching for the second character
			
			
			for(int i=k; i<n1; i++)
				for(int j=index; j<n2; j++)
					if(str1.charAt(i) == str2.charAt(j) )
					{
						cur++;
						index = j+1;
						break;
					}
			
			if(cur > max)
				max = cur;
		}
		
		return max;
	}
	
	//Recursion
	static int longestCommonSubsequence1(String str1, String str2, int n1, int n2)
	{
		if(n1==0 || n2==0)
			return 0;
		
		if(str1.charAt(n1-1) == str2.charAt(n2-1))
			return 1 + longestCommonSubsequence1(str1, str2, n1-1, n2-1);
		
		return Math.max( longestCommonSubsequence1(str1, str2, n1-1, n2), 
				longestCommonSubsequence1(str1, str2, n1, n2-1) );
	}
	
	//DP
	static int longestCommonSubsequence2(String str1, String str2)
	{
		int n1 = str1.length();
		int n2 = str2.length();
		
		int mat[][] = new int[n1+1][n2+1];
		
		for(int[] x: mat)
			Arrays.fill(x, 0);
		
		for(int i=1; i<=n1; i++)
		{
			for(int j=1; j<=n2; j++)
			{
				if( str1.charAt(i-1) == str2.charAt(j-1) )
					mat[i][j] = mat[i-1][j] + 1;
				else
					mat[i][j] = Math.max(mat[i][j-1], mat[i-1][j]);
			}
		}
		
		for(int[] x: mat)
		{
			for(int y: x)
				System.out.print(y + "\t");
			System.out.println();
		}
		
		return mat[n1][n2];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the first string : ");
		String str1 = s.next();
		
		System.out.print("Enter the second string : ");
		String str2 = s.next();
		
		int ans = longestCommonSubsequence1(str1, str2, str1.length(), str2.length());
		System.out.println(ans);
		
		s.close();
	}

}