当前位置：首页 > article >正文

多维动态规划-面试高频！-最长公共子序列和最长公共子串、回文串-c++实现和详解

article 2024/12/25 21:38:52

1143. 最长公共子序列

中等

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

解法

定义 dp [ i ] [ j ] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。状态定义特别重要，dp[ i] [ j] 其中i和j都是开区间，所以dp[0] [0]=0只是表示两个空串的最长公共子序列，这种方式省去了所有的初始化

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 状态定义特别重要
        // dp[i][j] i和j都是开区间
        // 如果上一个都相等，就给下一个赋值
        // 遍历只是表现形式
        int M = text1.size();
        int N = text2.size();
        // dp的初始化
        vector<vector<int>> dp(M + 2, vector<int>(N + 2, 0));
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[M][N];
    }
};

BM66 最长公共子串

题目链接-牛客

这道题我面试碰到了，当时不会做！没想到力扣没有这道题！

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

数据范围： 1≤∣𝑠𝑡𝑟1∣,∣𝑠𝑡𝑟2∣≤50001≤∣str1∣,∣str2∣≤5000
要求：空间复杂度 𝑂(𝑛2)O(n2)，时间复杂度 𝑂(𝑛2)O(n2)

示例1

输入：

"1AB2345CD","12345EF"

复制

返回值：

"2345"

复制

备注：

1≤∣𝑠𝑡𝑟1∣,∣𝑠𝑡𝑟2∣≤5 0001≤∣str1∣,∣str2∣≤5000

解法

本题的区别是子序列和子串的定义不同，所以本题如果两个字符不同的话就应该直接把dp清零！

我自己的代码如下：

#include <vector>
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 M = str1.size();
        int N = str2.size();
        int maxx = 0;
        vector<vector<int>>dp(M + 2, vector<int>(N + 2, 0)); //初始化、
        string res;
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxx) {
                        maxx = dp[i][j];
                        int l = dp[i][j];
                        res = str1.substr(i - l, l);
                    }
                } else dp[i][j] = 0;
            }
        }
        return res;
    }
};

后来看到别人更好的代码：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string LCS(const string& str1, const string& str2) {
    int maxLength = 0; // 记录最长公共子串的长度
    int maxLastIndex = 0; // 记录最长公共子串最后一个字符在字符串str1中的位置

    // 创建二维动态规划表，大小为(str1.length() + 1) x (str2.length() + 1)
    vector<vector<int>> dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));

    // 遍历str1和str2的每一个字符
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            // 当字符相等时，更新dp表的值
            if (str1[i] == str2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;

                // 如果当前公共子串的长度大于之前记录的最大值，则更新最大长度和最后一个字符的位置
                if (dp[i + 1][j + 1] > maxLength) {
                    maxLength = dp[i + 1][j + 1];
                    maxLastIndex = i;
                }
            } else {
                // 当字符不相等时，将dp表中的值设为0，表示没有公共子串
                dp[i + 1][j + 1] = 0;
            }
        }
    }

    // 使用substr函数截取最长公共子串
    return str1.substr(maxLastIndex - maxLength + 1, maxLength);
}

这里补充一个点，求回文串、回文数等等的通法：双指针中心扩散

最长回文串

我先贴一份我自己写的代码，我的初始想法是，把s做一个reverse，然后求s1和s的最长公共子串，就是回文串

class Solution {
public:
    string longestPalindrome(string s) {
        // 最长回文子串=reverse的最长公共子串！
        string s1 = s;
        reverse(s.begin(), s.end());
        int M = s.size();
        vector<vector<int>> dp(M + 1, vector<int>(M + 1, 0));
        int maxlen = 0;
        int end = 0;
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= M; j++) {
                if (s[i - 1] == s1[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxlen) {
                        maxlen = max(maxlen, dp[i][j]); // 最大值
                        end = i - 1;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return s.substr(end - maxlen + 1, maxlen);
    }
};

样例都过了，卡在了后面的一个样例，说明这个方法是错的！
下面附正确的代码(已经写上完整注释）：

class Solution {
public:
    // 辅助函数，用于计算以 s[l] 和 s[r] 为中心的最长回文子串的长度
    int help(string s, int l, int r) {
        int len = s.size();

        // 当 l 和 r 不超出范围，并且 s[l] == s[r] 时，向外扩展
        while (l >= 0 && r < len && s[l] == s[r]) {
            l--;  // 左边指针左移
            r++;  // 右边指针右移
        }
        // 返回回文子串的长度，注意此时 l 和 r 已经多走了一步
        return r - l - 1; // 回文串的长度为 r - l - 1
    }

    // 主函数，返回最长的回文子串
    string longestPalindrome(string s) {
        int len = s.size();  // 字符串长度
        int begin = 0;  // 记录最长回文子串的起始位置
        int maxlen = 0; // 记录最长回文子串的长度

        // 遍历字符串中的每个字符，以它们作为回文的中心
        for (int i = 0; i < len; i++) {
            // 以 i 为中心扩展，找奇数长度的回文子串
            int len1 = help(s, i, i);
            // 以 i 和 i+1 为中心扩展，找偶数长度的回文子串
            int len2 = help(s, i, i + 1);

            // 更新最长回文子串的长度和起始位置
            if (len1 > maxlen || len2 > maxlen) {
                if (len1 > len2) {
                    // 如果奇数长度的回文子串更长
                    maxlen = len1;  // 更新最大长度
                    begin = i - (len1 - 1) / 2; // 计算起始位置
                } else {
                    // 如果偶数长度的回文子串更长
                    maxlen = len2;  // 更新最大长度
                    begin = i - (len2 - 2) / 2; // 计算起始位置
                }
            }
        }
        // 返回从起始位置开始的最大回文子串
        return s.substr(begin, maxlen);
    }
};