题解 | #最长公共子串#

最长公共子串

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

最长公共子序列的简化版本,字串要求必须连续。

#include <utility>
#include <vector>
class Solution {
  public:
    string LCS(string str1, string str2) {
        int len1 = str1.size(), len2 = str2.size();
        vector<vector<int>> dp(len1, vector<int>(len2, 0));
        int maxlen = 0;
        pair<int, int> maxindex;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = i * j ? dp[i - 1][j - 1] + 1 : 1;
                    if (dp[i][j] > maxlen) {
                        maxlen = dp[i][j];
                        maxindex = {i, j};
                    }
                }
            }
        }
        string res("");
        for (int k = maxindex.first, c = maxlen - 1; c >= 0;
                k--, c--) {
            res.insert(0, 1, str1[k]);
        }
        return res;
    }
};

全部评论

相关推荐

07-10 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
07-09 18:33
门头沟学院 Java
这么逆天每年都有人去???&nbsp;填多益网申就是大型的服从性测试
鲁大牛:辅导员在群里发了这个公司我就申了一下。网申居然要写当场开摄像头写两篇不少于三百字的作文。太逆天了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务