题解 | #最长公共子串#

java版

思路： 以String[][] res 来保存先前状态，res[i][j] 代表str1到i、str2到j的公共串, 注意如果str1.charAt(i) != str2.charAt(j) , 则res[i][j] = ""；

递推公式为：

如果 str1.charAt(i) == str2.charAt(j)

res[i][j] = str1.charAt(i-1) == str2.charAt(j-1) ? res[i-1][j-1] + str1.charAt(i) : str1.charAt(i) + "";

否则

 res[i][j] = str1.charAt(i) == str2.charAt(j) ?  str1.charAt(i) + "" : "";

注意边界i-1 < 0 和 j - 1 < 0 的处理，还有就是这种定义的状态不连续，需要设置 lcs来记录过程中的最长串

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        // write code here
        int m = str1.length(), n = str2.length();
        String[][] res = new String[m][n];
        String lcs = "";
        for(int i = 0; i < m; i++)
            Arrays.fill(res[i], "");
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i - 1 >= 0 && j - 1 >= 0){
                    if(str1.charAt(i) == str2.charAt(j)){
                        res[i][j] = str1.charAt(i-1) == str2.charAt(j-1) ? res[i-1][j-1] + str1.charAt(i) : str1.charAt(i) + "";
                    }
                }else {
                    res[i][j] = str1.charAt(i) == str2.charAt(j) ?  str1.charAt(i) + "" : "";
                }
                lcs  =   res[i][j].length() > lcs.length() ? res[i][j] : lcs;
            }
        }
        return lcs;
    }
}