给定两个字符串str1和str2,输出两个字符串的最长公共子串（动态规划）

知识点 动态规划 描述 给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。

数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000 要求： 空间复杂度 O(n^2)O(n 2 )，时间复杂度 O(n^2)O(n 2 ) 示例1 输入： “1AB2345CD”,“12345EF” 复制 返回值： “2345”

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* longest common substring

* @param str1 string字符串 the string

* @param str2 string字符串 the string

* @return string字符串

*/

public String LCS (String str1, String str2) {

// write code here

int maxL = 0;

int maxI = 0;

int[][] dp = new int[str1.length()+1][str2.length()+1];

for(int i =0;i

for(int j = 0;j

if(str1.charAt(i)==str2.charAt(j)){

dp[i+1][j+1] =dp[i][j]+1;

if(dp[i+1][j+1]>maxL){//选max值

maxL = dp[i+1][j+1];

maxI = i;//最后一个元素

}

}else{

dp[i+1][j+1] = 0;

}

}

}

return str1.substring(maxI-maxL+1,maxI+1);

}

}

参考文章