NC92 最长公共子序列-II

最开始 还是有小bug

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        int[][] dp = new int[s1.length()+1][s2.length()+1];

        for(int i=1;i<=s1.length();i++){
            for(int j=1;j<=s2.length();j++){
                if(ch1[i-1] == ch2[j-1])
                {dp[i][j] = dp[i-1][j-1]+1;}
                else
                {dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);}
            }
        }

        if(dp[s1.length()][s2.length()] == 0) return "-1";
        String res = ""; 

        for(int i=s1.length(), j=s2.length();i>=1 && j>=1;){
            if(ch1[i-1] == ch2[j-1]){
                res = ch1[i-1] + res;
                i--;j--;
            }else if(dp[i][j-1]>=dp[i-1][j]) j--;
            else if(dp[i][j-1] < dp[i-1][j]) i--;
        }

        return res;

    }
}

两种状态 动态规划 dp[i][j]分别代表这个长度的i，j位置上的最长公共长度

最后从最后一个开始判断，往前回溯；

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        if(s1.length() < s2. length()){
            arr1 = s2.toCharArray();
            arr2 = s1.toCharArray();
        }


        int max = 0;

        int[][] dp = new int[arr2.length+1][arr1.length+1];
        for(int i =1; i<=arr2.length;i++) {
            for(int j =1; j<=arr1.length;j++){
                if(arr2[i-1] == arr1[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1; // 原来写的是 Math.max(dp[i-1][j], dp[i][j-1]) + 1; 没通过？
                    if(dp[i][j] > max){
                        max = dp[i][j];
                    }
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        if(max == 0){
            return "-1";
        }

        char[] str = new char[max];
        for(int i=arr2.length, j = arr1.length; dp[i][j] >= 1;){
            if(arr2[i-1] == arr1[j-1]){
                str[max-1] = arr2[i-1];
                i--;j--;
                max--;
            }
            else if(dp[i-1][j] >= dp[i][j-1]){
                i--;
            }
            else j--;
        }
        return new String(str);
    }
}