描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。

示例1

输入：
“1AB2345CD”,”12345EF”

返回值：
“2345”

  1. import java.util.*;
  4. public class Solution {
  5.     /**
  6.      * longest common substring
  7.      * @param str1 string字符串 the string
  8.      * @param str2 string字符串 the string
  9.      * @return string字符串
  10.      */
  11.     public String LCS (String str1, String str2) {
  12.         //记录最长公共子串的长度
  13.         int maxLength = 0;
  14.         //记录最长公共子串最后一个元素在字符串str1中的位置
  15.         int maxLastIndex = 0;
  16.         int[][] dp = new int[str1.length() + 1][str2.length() + 1];
  18.         for(int i=0; i<str1.length(); i++){
  19.             for(int j = 0; j < str2.length(); j++){
  20.                 //递推公式，两个字符相等的情况
  21.                 if(str1.charAt(i) == str2.charAt(j)){
  22.                     dp[i+1][j+1] = dp[i][j] + 1;
  23.                     //如果遇到了更长的子串，要更新，记录最长子串的长度，
  24.                     //以及最长子串最后一个元素的位置
  25.                     if(dp[i+1][j+1] > maxLength){
  26.                         maxLength = dp[i+1][j+1];
  27.                         maxLastIndex = i;
  28.                     }
  29.                 } else{
  30.                     //递推公式，两个字符不相等的情况
  31.                     dp[i+1][j+1] = 0;
  32.                 }
  34.             }
  35.         }
  36.         //最字符串进行截取，substring(a,b)中a和b分别表示截取的开始和结束位置
  37.         return str1.substring(maxLastIndex-maxLength+1,maxLastIndex +1);
  38.     }
  39. }