LeetCode 647回文子串 647回文子串 | 代码随想录25期训练营day57

发布时间:2023年12月20日

动态规划算法14

LeetCode 647 回文子串 2023.12.20

int countSubstrings(string s) {
    //暴力搜索,前两层遍历确定子字符串的起始和末尾位置
    //第三层循环判断当前子字符串是否为回文串
    /*
        int result = 0;
        for (int i = 0; i < s.size(); i++)
        {
            for(int j = i; j < s.size(); j++)
            {
                //sym变量用于记录判断结果,当不是回文串时,sym值变
                int sym = 1;
                for (int k = i; k <= (j+i)/2; k++)
                {
                    if(s[k] != s[j-(k-i)])
                    {
                        sym = 0;
                        break; 
                    }
                }
                if(sym == 1)
                    result++;
            }
        }
        return result;*/

    //动态规划
    //result存储s字符串中回文子串的个数
    int result = 0;
    //1确定二维dp数组,dp[i][j]表示s[i, j]子串是否为回文串
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    //3初始化,根据递推公式含义,dp所有值默认值为false
    //2确定递推公式 4确定遍历顺序
    //dp[i][j]由dp[i+1][j-1]得出,那么二层循环先倒序后正序
    for (int i = s.size()-1; i >= 0; i--)
    {
        for(int j = i; j < s.size(); j++)
        {
            //递推公式:当s[i, j]子字符串首尾元素相同时
            //当j-i<=1时,那么说明只有一个元素或者三个元素中首尾元素相同
            //当j-i>1时,判断s[i+1, j-1]是否为回文串,如果是,那么s[i, j]也是回文串
            if(s[i] == s[j])
            {
                if(j-i <= 1)
                {
                    dp[i][j] = true;
                    result++;
                }
                else
                {
                    if(dp[i+1][j-1])
                    {
                        dp[i][j] = true;
                        result++;
                    }
                }
            }

        }
    }
    return result;
}

LeetCode 517 最长回文子序列 2023.12.20

int longestPalindromeSubseq(string s) {
    //1确定dp数组,dp[i][j]表示s[i, j]区间内最长回文子序列的长度
    vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
    //3初始化,根据递推公式含义,需要对i=j时dp[i][j]赋值长度为1
    for (int i = 0; i < s.size(); i++)
        dp[i][i] = 1;
    //2确定递推公式 4确定遍历顺序
    //dp[i][j]由dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]得出,那么二层循环先倒序后正序
    for (int i = s.size()-1; i >= 0; i--)
    {
        for(int j = i + 1; j < s.size(); j++)
        {
            //当s[i] == s[j]时,dp[i][j]=dp[i+1][j-1]+i,j两个字符长度
            if(s[i] == s[j])
                dp[i][j] = dp[i+1][j-1] + 2;
            //当s[i] == s[j]时,dp[i][j]=max(在dp[i+1][j-1]基础上加s[i]或s[j]的最长回文子序列长度)
            else
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }
    //返回s[0,s.size()-1]的最长回文子序列长度
    return dp[0][s.size()-1];
}

文章来源:https://blog.csdn.net/weixin_66706867/article/details/135106044
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。