每天一道算法题18

【最长公共子序列，子串】给定两个字符串上str1 和 str2， 求两个字符的最长公共子序列和最长公共子串。

1. 最长公共子序列

public static int[][] getDp(String str1, String str2) {
    int[][] dp = new int[str1.length][str2.length];
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();

    dp[0][0] = s1[0] == s2[0] ? 1:0;
    for (int i = 1; i < str1.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], (s1[i] == s2[0] ? 1:0));
    }

    for (int j = 1; j < str2.length; j++) {
        dp[0][j] = math.max(dp[0][j-1], (s2[j] == s1[0] ? 1:0))
    }

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

    return dp;
}

public static String lcse(String str1, String str2) {
    int m = str1.length - 1;
    int n = str2.length - 1;
    int[][] dp = new int[m+1][n+1];
    dp = getDp(str1, str2);
    char[] res = new char[dp[m][n]];
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();

    if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
        return "-1";
    }

    int index = res.length - 1;
    while(index >= 0) {
        if (n > 0 && dp[m][n] == dp[m][n-1]) {
            n--;
        } else if (m > 0 && dp[m][n] == dp[m-1][n]) {
            m--;
        } else {
            res[index--] = s1[m];
            m--;
            n--;
        }
    }
    return String.valueOf(res);
}

2. 最长公共子串
   最长公共子串相对最长公共子序列更简单一点，因为最长公共子串是需要连续的，所以只需要和对角线进行比较
   即可。

public class LongestPublicCharaterString {
    public static int[][] getDp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str[0]) {
                dp[i][0] = 1;
            }
        }

        for (int j = 0;  j < str2.length; j++) {
            if (str2[j] == str1[0]) {
                dp[0][j] = 1;
            }
        }

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

        return dp;
    }

    public static String lcst1(String str1, String str2) {
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return "";
        }

        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int[][] dp = getDp(s1, s2);
        int end = 0; 
        int max = 0;
        for(int i = 0; i < s1.length; i++) {
            for (int j = 0; j < s2.length; j++) {
                if (dp[i][j] > max) {
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        return str1.substring(end - max + 1, end + 1);
    }
}