Classic Problem - ShuweiLeung/Thinking GitHub Wiki

  1. 最长公共子字符串 Longest common substring

【题目描述】

Given two strings, find the longest common substring.Return the length of it.

给出两个字符串,找到最长公共子串,并返回其长度。

【注意】:子串的字符应该连续的出现在原字符串中,这与子序列有所不同。dp[i][j]是以str1[i],str2[j]为尾的最长公共子字符串

    public int longestCommonSubstring(String A, String B) {
        // state: f[i][j] is the length of the longest lcs
        // ended with A[i - 1] & B[j - 1] in A[0..i-1] & B[0..j-1]
        int n = A.length();
        int m = B.length();
        int[][] f = new int[n + 1][m + 1];
        
        // initialize: f[i][j] is 0 by default
        
        // function: f[i][j] = f[i - 1][j - 1] + 1 or 0
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = 0; //注意该处语句和最长公共子序列语句不同
                }
            }
        }
        
        // answer: max{f[i][j]}
        int max = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                max = Math.max(max, f[i][j]);
            }
        }
        
        return max;
    }
  1. 最长公共子序列 Longest Common Subsequence

【Description】

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

注意最长公共子序列(本题)和最长公共子串(Longest Common Substring 解题报告)的区别。

最长公共子序列不要求连续,即子序列里的两个相邻字符在原串中不一定相邻,只是前后顺序一致。

设有两字符串A,B,构建状态数组dp[A.length][B.length]

设dp[i][j]为A[0…i], B[0…j]的最长公共子序列,注意dp[i][j]的定义与最长公共子字符串不同,是前i个和前j个字符的公共子序列

则有状态方程

1. X[i] == Y[j],dp[i][j] = dp[i-1][j-1] + 1
2. X[i] != Y[j],dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);

对于上述状态转移方程,我们可以通过下面这段内容来理解:

public int longestCommonSubsequence(String A, String B) {
    if(A == null || B == null || A.isEmpty() || B.isEmpty()){ 
        return 0; 
    } 
    
    int n = A.length(); 
    int m = B.length(); 
    int dp[][] = new int[n+1][m+1]; 
    int lcs = 0; 

    for(int i = 0 ; i < n; i ++){ 
        for(int j = 0 ; j < m;j ++){ 
            if(A.charAt(i) == B.charAt(j)){ 
                dp[i+1][j+1] = 1 + dp[i][j]; 
                lcs = Math.max(dp[i+1][j+1],lcs); 
            }
            else
                dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);   //注意该处与最长公共子字符串语句不同
        }
    } 
    return lcs; 
}