题解 | #最长公共子序列-II#(动态规划且得到字符串结果)

最长公共子序列-II

http://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11

  1. dp[i][j]:str1中以第i位置结尾和str2中以第j个位置结尾的两个字符的最长公共子序列
  2. 初始化:dp[i][0]和dp[0][j] 因为某一个字符串0位置没有长度所以公共长度为0
  3. 根据dp,从后往前,查找结果。
class Solution {
    /*
    dp[i][j]:str1中以第i位置结尾和str2中以第j个位置结尾的两个字符的最长公共子序列
    初始化:dp[i][0]和dp[0][j] 因为某一个字符串0位置没有长度所以公共长度为0
    dp[i][j] =  dp[i-1][j-1] + 1   当(s1[i-1] == s2[j-1])时。
            max(dp[i-1][j], dp[i][j-1]);  others
    根据dp,从后往前,查找结果。
    */
public:
    string LCS(string s1, string s2) {
        if(s1.empty() || s2.empty()) return "-1";  // 边界
        int dp[s1.size()+1][s2.size()+1]; // dp数组
        // 初始化
        for(int i = 0; i <= s1.size(); i++) 
            dp[i][0] = 0;
        for(int j = 0; j <= s2.size(); j++) 
            dp[0][j] = 0;
        for(int i = 1; i <= s1.size(); i++) {
            for(int j = 1; j <= s2.size(); j++) 
                dp[i][j] = (s1[i-1] == s2[j-1]) ? dp[i-1][j-1] + 1: max(dp[i-1][j], dp[i][j-1]); 
        }
        string res = "";
        for(int i = s1.size(), j = s2.size(); dp[i][j] >= 1;) {
            if(s1[i-1] == s2[j-1]) {
                res += s1[i-1];
                i--;j--;
            }
            else if(dp[i-1][j] >= dp[i][j-1]) i--;
            else j--;
        }
        reverse(res.begin(), res.end());
        return res.empty() ? "-1" : res;
    }
};

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-09 21:15
清华大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
2022-12-10 18:47
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议