题解 | #最长公共子串#

最长公共子串

http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac

题意：

求两个字符串的最长公共子串。

方法一：暴力法

对于str1和str2的最长公共子串，最直接的办法就是穷举他们的子串并判断是否是公共拥有的。

思路：（1）穷举两字符串起始位置（2）寻找以该起始位置开始的公共子串，判断是否是最长的并更新

代码如下：

class Solution {
public:
  /**
   * longest common substring
   * @param str1 string字符串 the string
   * @param str2 string字符串 the string
   * @return string字符串
   */
  string LCS(string str1, string str2) {
      // write code here
      //startIndex是最长公共子串在str1中的开始位置，maxLen是长度
      int startIndex=0,maxLen=0;
      int len1=str1.size(),len2=str2.size();
      //双重循环，分别是str1的开始位置和str2的开始位置
      for(int start1=0;start1<len1;start1++){
          for(int start2=0;start2<len2;start2++){
              int i=start1,j=start2,len=0;
              //判断字符串是否相等，以及长度
              while(i<len1&&j<len2&&str1[i++]==str2[j++])
                  len++;
              //超过当前最大长度，更新startIndex和maxLen
              if(len>maxLen){
                  startIndex=start1;
                  maxLen=len;
              }
          }    
      }
      //返回最长公共子串
      return str1.substr(startIndex,maxLen);
  }
};

复杂度分析：

时间复杂度： $O(m*n^2)$ ，双重循环穷举起始位置，while循环寻找公共子串。其中m,n分别是两字符串的长度，且n<m。
空间复杂度： $O(1)$ ，仅常数个临时变量。

方法二：动态规划

方法一中的解法存在很多子问题重叠的情况，有较大的改进空间。基于此，可以使用动态规划的方法，寻找最优子结构并用额外空间保存子问题的解，以此来避免在解决同样的问题上花费时间。
思路：二维数组dp[i][j]，表示在str1中以位置i结尾，和在str2中以位置j结尾的最长公共子串的长度。有如下递推式：
(1) if str1[i]!=str2[j] -> dp[i][j]=0
(2) if str1[i]==str2[j] -> dp[i][j]=dp[i-1][j-1]+1

式（1）显然，若两字符串结尾的字符不等，则最长公共子串长度为0。式（2）表示两字符串结尾字符相等，则依赖于删除该相等的字符之后的两字符串的最长公共子串。如下是具体例子的图解以方便理解。

图解如下：

如下是数组dp的产生过程，其中str1="1AB2345CD", str2="12345EF".
图片说明

代码如下：

class Solution {
public:
  /**
   * longest common substring
   * @param str1 string字符串 the string
   * @param str2 string字符串 the string
   * @return string字符串
   */
  string LCS(string str1, string str2) {
      // write code here
      int len1=str1.size(),len2=str2.size();
      //endIndex是最长公共子串在str1中的结束位置
      int endIndex=-1,maxLen=0;
      //二维数组dp，其内的值默认为0。维度为(len1+1)*(len2+1)
      //其中dp[0][?]和dp[?][0]为辅助的单元，用于递推式的起始条件，相比于上述递推式有所变化。
      vector<vector<int>> dp(len1+1,vector<int>(len2+1));
      for(int i=1;i<=len1;i++){
          for(int j=1;j<=len2;j++){
              //相等则更新dp[i][j],否则仍然为0
              if(str1[i-1]==str2[j-1]){
                  dp[i][j]=dp[i-1][j-1]+1;
                  //更新maxLen和endIndex
                  if(dp[i][j]>maxLen){
                      maxLen=dp[i][j];
                      endIndex=i-1;
                  }
              }
          }
      }
      int startIndex=endIndex-maxLen+1;
      return str1.substr(startIndex,maxLen);
  }
};