class Solution { public int longestCommonSubsequence(String text1, String text2) { int m = text1.length() , n = text2.length(); return solve(text1 , text2 , m-1 , n-1 , new Integer[m][n]); //tabulization-> m*n //right shifting of idexes to solve base case in tabulization int dp[][] = new int[m+1][n+1]; for(int i = 1 ;i < m+1 ; i++){ for(int j = 1 ; j < n+1 ; j++){ char ch1 = text1.charAt(i-1) , ch2 = text2.charAt(j-1); if(ch1 == ch2) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } return dp[m][n]; } //Recursion(2^(m*n)) Memo(m*n) | sc m*n + m*n public int solve(String text1 , String text2 , int i , int j, Integer[][]dp ){ if(i < 0 || j < 0) return 0; if(dp[i][j] != null) return dp[i][j]; char ch1 = text1.charAt(i) , ch2 = text2.charAt(j); if(ch1 == ch2) return dp[i][j] = 1+ solve(text1 , text2 , i-1 , j-1 , dp); else{ int fact = Math.max(solve(text1,text2 ,i-1,j,dp) , solve(text1,text2 ,i,j-1,dp)); return dp[i][j] = 0 +fact; } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter