LeetCode Longest Common Substring

题目

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

Examples :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input : X = "GeeksforGeeks", y = "GeeksQuiz"
Output : 5
The longest common substring is "Geeks" and is of
length 5.

Input : X = "abcdxyz", y = "xyzabcd"
Output : 4
The longest common substring is "abcd" and is of
length 4.

Input : X = "zxabcdezy", y = "yzabcdezx"
Output : 6
The longest common substring is "abcdez" and is of
length 6.

理解

求字符串X,Y的公共最长子串,这些子串要求连续性,类似的问题是求公共最长子序列

解决

设 m = X.length(), n = Y.length();

Brute Force(暴力法)

思路:

  1. 遍历所有X的子串,时间复杂度为O(m^2)
    1
    2
    3
    4
    5
    for(int i=0; i<X.length(); i++){
    for(int j=0; j<X.length(); j++){
    String sub = X.substring(i, j+1);
    }
    }
  2. 求子串是否也是Y的子串,即子串在Y中的位置,可选择KMP算法,时间复杂为O(n)
  3. 满足条件的最大长度的子串就是最长公共子串。最终时间复杂度为:O(n * m^2)

Dynamic Programming(动态规划)

思路:

  1. 设 X = “abcdxyz”, Y = “xyzabcd”
  2. 先求解如下子符串组的公共后缀:
    1
    2
    3
    4
    5
    1. X_6="abcdxyz", Y_6="xyzabcd" ===> 公共后缀长度:0
    2. ...
    3. X_3="abcd", Y_6="xyzabcd" ===> 公共后缀长度:4
    4. ...
    5. X_0="a", Y_0="x" ===> 公共后缀长度:0
  3. 上面所有子符串组的最长公共后缀,就是最长的公共子串:”abcd“

求X,Y的公共最长子串问题,转换为求所有子串的最长公共后缀的问题,公共后缀问题,有如下状态转移方程:

1
2
3
4
5
6
7
The longest common suffix has following optimal substructure property
LCSuff(X, Y, m-1, n-1) = LCSuff(X, Y, m-2, n-2) + 1 if X[m-1] = Y[n-1]
0 Otherwise (if X[m-1] != Y[n-1])

The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m-1, n-1) = Max(LCSuff(X, Y, i, j)) where 1 <= i < m
and 1 <= j < n

代码实现:

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
public class LongestCommonSubSequence { 
public int LCSubStr(String X, String Y) {
if(X == null || X.length() == 0){
return 0;
}
if(Y == null || Y.length() == 0){
return 0;
}

int m = X.length();
int n = Y.length();

int LCStuff[][] = new int[m][n];
int maxLCSLen = 0; // 最长公共后缀长度

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (X[i] == Y[j]) {

if(i==0 || j==0){
LCStuff[i][j] = 1;
} else {
LCStuff[i][j] = LCStuff[i - 1][j - 1] + 1;
}

maxLCSLen = Math.max(maxLCSLen, LCStuff[i][j]);
} else {
LCStuff[i][j] = 0;
}
}
}
return maxLCSLen;
}
}

复杂度:

  1. 时间复杂度:O(m * n)
  2. 空间复杂度:O(m * n)

参考

  1. Longest Common Substring | DP-29
感谢您的阅读,本文由 刘阳 版权所有。如若转载,请注明出处:刘阳(https://handsomeliuyang.github.io/2018/12/15/%E6%97%A5%E5%B8%B8%E5%AD%A6%E4%B9%A0-Leetcode-longest-common-substring/
LeetCode Longest Palindromic Substring
LeetCode Regular Expression Matching