用动态规划法解题。
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 if (str1 == null || str2 == null || str1.equals(" ") || str2.equals(" ")) { return "-1"; } //动态规划 二维数组,斜下来就是最长字串 int str1len = str1.length(); int str2len = str2.length(); int maxLen = 0; int index = 0; // 定义一个二维数组 int[][] dp = new int[str1len][str2len]; //第一步:划分 for (int i = 0; i < str1len; i++) { for (int j = 0; j < str2len; j++) { if (str1.charAt(i) == str2.charAt(j)) { //防止数组越界 if (j * i ==0){ dp[i][j]=1; //if条件语句保证maxLen不被破坏 if(maxLen < dp[i][j]){ maxLen = dp[i][j]; index = i; } } else{ dp[i][j] = dp[i - 1][j - 1] + 1; //if条件语句用来更新maxLen if(maxLen < dp[i][j]){ maxLen = dp[i][j]; index = i; } } } } } if( maxLen==0 ){ return "-1"; } return str1.substring(index-maxLen+1,index+1); } }