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

public String LCS(String str1, String str2) {
        if(str1==null||str2==null||str1.length()==0||str2.length()==0){
            return null;
        }

        int m = str1.length();
        int n = str2.length();

        String[][] dp = new String[m+1][n+1];
        String ans ="";
        for(int i=0;i<=m;i++){
            dp[i][0]="";
        }

        for(int j=0;j<=n;j++){
            dp[0][j]="";
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+str1.charAt(i-1);

                }else{
                    dp[i][j]="";
                }
                String tempString = dp[i][j];
                ans = ans.length()>tempString.length()?ans:tempString;
            }
        }

        
        return ans.length()>0?ans:null;


    }