题解 | #最长公共子串#

最长公共子串

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

最长公共子串
问题描述：给定两个字符串str1和str2,输出两个字符串的最长公共子串，题目保证str1和str2的最长公共子串存在且唯一。
示例1
输入："1AB2345CD","12345EF"
返回："2345"
问题分析
子串要求这串字符串在原字符串中是连续的，要区别于子序列的概念。

方法一
思路分析
本题如果采用手动求解的方法，即从第一个子串的起始位置str1[i]（i=0,1,2...）出发，与第二个子串的起始位置str2[j](j=0,1,2...)字符开始比较，直到找到相同的字符，接着记录此时的m=i,n=j，继续在两个子串中比较，记录公共子串长度为length，如果没有相同字符，则继续从第一个子串的str[i+1]出发与第二个子串的起始位置str2[j](j=0,1,2...)字符开始比较，即存在内外两层循环遍历。因此该方法为暴力搜索。
实例分析
给定子串“1A23”“123”，找到最大的length即可，并记录最长公共子串在str1中的位置，如下所示

C++核心代码

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 strlen1=str1.size(),strlen2=str2.size();
      if(strlen1==0||strlen2==0)
          return 0;
      int start1=0,maxlen=0;//start1表示字串在str1中的开始位置，mexlen记录最长公共子串的长度
      int comparisons = 0;
      for(int i=0;i<strlen1;i++)
      {
          for(int j=0;j<strlen2;j++)
          {
              int length = 0;//用于记录当前公共子串的长度
              int m = i;//用于记录子串在strl，没有发生越界
              int n = j;//用于记录子串在str2，没有发生越界
              while(m <strlen1 && n < strlen2)//寻找公共子串，不一定是最长的
              {
                  ++comparisons;
                  if (str1[m] != str2[n]) break;
                  ++length;
                  ++m;
                  ++n;
              }
              if (maxlen < length)
              {
                  maxlen = length;//更新最长公共子串的长度
                  start1 = i;//当前最长公共子串在str1中的开始位置
              }
              
              
          }
      }
      return str1.substr(start1,maxlen);
  }
};

复杂度分析
• 时间复杂度：两层循环遍历，但由于存在对字符串的比较，因此时间复杂度要大于$O(str1.len*str2.len)$
• 空间复杂度: 借助了几个变量，因此空间复杂度为$O(1)$

方法二
思路分析
直接通过穷举的办法可以将两个字符串中的所有公共子串找到，但是时间复杂度很大，因此考虑使用动态规划的办法，即将前面的子问题答案记录下来，从而对后面的问题提供帮助。因此我们可以定义一个二维数组$dp[str1.len][str2.len]$，可以想象将两个字符串放在二维数组相应的位置，如果相应位置的字符相等，则$dp[i][j]=1$，在计算第i个位置时，可以根据第[i-1][j-1]位置确定，由此形成相应的状态转移方程。具体的步骤如下：
• 定义一个二维数组$dp[str1.len][str2.len]$，maxlen表示最长公共子串长度，endinx表示子串在str1结束的位置
• 如果是在行头或列头，表示开始位置，所以$dp[i][j]=1$ 第一次出现
• 两层循环遍历，当相应位置上字符相等时$dp[i][j]=dp[i-1][j-1]+1$，否则记为0
• 不断更新maxlen，endinx直到循环结束

实例分析

分析如图所示，给定字符串"1AB2345CD","12345EF"

C++核心代码

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 strlen1=str1.size(),strlen2=str2.size();
      int endindex=0,maxlen=0;//endIndex是最长公共子串在str1中的结束位置
      vector<vector<int>> dp(strlen1,vector<int>(strlen2));//定义二维辅助数组用于存储相应位置上的字符是否相等
      for(int i=0;i<strlen1;i++)
      {
          for(int j=0;j<strlen2;j++)
          {
              if(str1[i]==str2[j])
              {
                  if(i==0||j==0) dp[i][j]=1;//判断是否为字符串的开始位置相等
                  else dp[i][j]=dp[i-1][j-1]+1;////相等则更新dp[i][j],否则仍然为0
              }
              else 
              {
                  dp[i][j]=0;
              }
              if(dp[i][j]>maxlen)
                {
                    maxlen=dp[i][j];//更新公共子串的最大数
                    endindex=i;//更新公共子串的结束位置
                }
              
          }
      }
      return str1.substr(endindex-maxlen+1,maxlen);
  }
};

复杂度分析
• 时间复杂度：两层循环遍历，外层遍历次数str1.len，内层遍历次数str2.len，因此时间复杂度为$O(str1.len*str2.len)$
• 空间复杂度:使用了一个二维的辅助数组$dp[str1.len][str2.len]$,因此空间复杂度为$O(str1.len*str2.len)$

题解 | #最长公共子串#

全站热榜