Q28 Longest Common Subsequence - LeetCode 1143
Sat Mar 25 2023 15:36:26 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
/* Q28 dp playlist , every cell denotes LCS for that coloumn string
with that row string
2)smallest problem on bottom left , biggest problem on 0,0
3)making 2d dp array , keeping text 1 on coloumn and text2 on row +1
for dash or empty string
*/
int m = text1.length() , n = text2.length();
int[][] dp = new int[m+1][n+1];
//last coloumn , last row will be 0 for dashes
// i represent text1 , j represent text2
for(int i = m-1 ; i>= 0 ; i--){
for(int j = n-1 ; j>=0 ; j--){
//if first chars are equal , diagonally right +1 will be ans
if(text1.charAt(i) == text2.charAt(j))
dp[i][j] = dp[i+1][j+1] + 1;
//else max (horizontal ,vertical) will be answer
else
dp[i][j] = Math.max(dp[i+1][j] , dp[i][j+1]);
}
}
return dp[0][0];
}
}
content_copyCOPY
https://leetcode.com/problems/longest-common-subsequence/
Comments