LeetCode Longest Common Substring
题目
Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.
Examples :
1 | Input : X = "GeeksforGeeks", y = "GeeksQuiz" |
理解
求字符串X,Y的公共最长子串,这些子串要求连续性,类似的问题是求公共最长子序列
解决
设 m = X.length(), n = Y.length();
Brute Force(暴力法)
思路:
- 遍历所有X的子串,时间复杂度为O(m^2)
1
2
3
4
5for(int i=0; i<X.length(); i++){
for(int j=0; j<X.length(); j++){
String sub = X.substring(i, j+1);
}
} - 求子串是否也是Y的子串,即子串在Y中的位置,可选择KMP算法,时间复杂为O(n)
- 满足条件的最大长度的子串就是最长公共子串。最终时间复杂度为:O(n * m^2)
Dynamic Programming(动态规划)
思路:
- 设 X = “abcdxyz”, Y = “xyzabcd”
- 先求解如下子符串组的公共后缀:
1
2
3
4
51. 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 - 上面所有子符串组的最长公共后缀,就是最长的公共子串:”abcd“
求X,Y的公共最长子串问题,转换为求所有子串的最长公共后缀的问题,公共后缀问题,有如下状态转移方程:
1 | The longest common suffix has following optimal substructure property |
代码实现:
1 | public class LongestCommonSubSequence { |
复杂度:
- 时间复杂度:O(m * n)
- 空间复杂度:O(m * n)
参考
感谢您的阅读,本文由 刘阳 版权所有。如若转载,请注明出处:刘阳(https://handsomeliuyang.github.io/2018/12/15/%E6%97%A5%E5%B8%B8%E5%AD%A6%E4%B9%A0-Leetcode-longest-common-substring/)