Leetcode-Daily-Problem/Longest_Common_Subsequence.java at main · vishnuthumpudi/Leetcode-Daily-Problem · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1.equals(text2))
           return text1.length();
         char tb1[] = text1.toCharArray();
        char tb2[] = text2.toCharArray();

        if(tb1.length > tb2.length) {
            int dp[] = new int[tb1.length + 1];
            for(int i = 0; i < tb2.length; i++) {
                int pc = 0, prc;
                for(int j = 0; j < tb1.length; j++) {
                    prc = pc;
                    pc = dp[j + 1];
                    if(tb2[i] == tb1[j]) {
                        dp[j + 1] = prc + 1;
                    } else {
                        dp[j + 1] = Math.max(pc, dp[j]);
                    }
                }
            }

            return dp[tb1.length];
        } else {
            int dp[] = new int[tb2.length + 1];
            for(int i = 0; i < tb1.length; i++) {
                int pc = 0, prc;
                for(int j = 0; j < tb2.length; j++) {
                    prc = pc;
                    pc = dp[j + 1];
                    if(tb1[i] == tb2[j]) {
                        dp[j + 1] = prc + 1;
                    } else {
                        dp[j + 1] = Math.max(pc, dp[j]);
                    }
                }
            }

            return dp[tb2.length];
        }
    }
}