_49LeetCode代碼随想錄算法訓練營第四十九天-動态規劃 | 647.回文子串、516.最長回文子序列

題目清單

647.回文子串
516.最長回文子序列
動态規劃總結篇

647.回文子串

代碼随想錄位址：https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html

題目

給你一個字元串

，請你統計并傳回這個字元串中回文子串的數目。

回文字元串是正着讀和倒過來讀一樣的字元串。

子字元串是字元串中的由連續字元組成的一個序列。

具有不同開始位置或結束位置的子串，即使是由相同的字元組成，也會被視作不同的子串。

示例 1：

輸入：s = "abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"

示例 2：

輸入：s = "aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000
s 由小寫英文字母組成

思路

動态規劃思路

個人認為不好了解。

咬死了隻有兩種基礎情況，也就是i和j指向同一個元素，第二個是i和j隻相差1，并且s[i] == s[j]。

動規五部曲：

确定dp數組（dp table）以及下标的含義

觀察回文串的性質，如下圖：

_49LeetCode代碼随想錄算法訓練營第四十九天-動态規劃 | 647.回文子串、516.最長回文子序列_49LeetCode代碼随想錄算法訓練營第四十九天-動态規劃 | 647.回文子串、516.最長回文子序列647.回文子串516.最長回文子序列動态規劃總結篇

如果 s[1]，s[2]，s[3] 是回文的，隻需要比較s[0]和s[4]元素是否相同，相同的話字元串S就是回文。

找到一種遞歸關系，判斷一個子字元串（字元串的下标範圍[i,j]）是否回文，依賴于，子字元串（下标範圍[i + 1, j - 1]））是否是回文。

将dp數組是要定義為二維dp數組。

布爾類型的dp[i] [j]：表示區間範圍[i,j] （注意是左閉右閉）的子串是否是回文子串，如果是dp[i] [j]為true，否則為false。

确定遞推公式

當s[i]與s[j]不相等，dp[i] [j]一定是false。

當s[i]與s[j]相等時，有三種情況

情況一：下标i 與 j相同，同一個字元例如a，當然是回文子串
情況二：下标i 與 j相差為1，例如aa，也是回文子串
情況三：下标：i 與 j相差大于1的時候，例如cabac，此時s[i]與s[j]已經相同了，我們看i到j區間是不是回文子串就看aba是不是回文就可以了，那麼aba的區間就是 i+1 與 j-1區間，這個區間是不是回文就看dp[i + 1] [j - 1]是否為true。

是以遞推公式如下：

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情況一 和 情況二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情況三
        result++;
        dp[i][j] = true;
    }
}

result就是統計回文子串的數量。

此處沒有考慮s[i]與s[j]不相等的時候，因為在初始化dp[i] [j]的時候，就初始為false。

dp數組如何初始化

是以dp[i] [j]初始化為false。

确定周遊順序

周遊順序根據遞推公式決定，由于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++) {
        if (s[i] == s[j]) {
            if (j - i <= 1) { // 情況一 和 情況二
                result++;
                dp[i][j] = true;
            } else if (dp[i + 1][j - 1]) { // 情況三
                result++;
                dp[i][j] = true;
            }
        }
    }
}

舉例推導dp數組

草稿紙。

雙指針思路

中心點向外擴散的思想：

在周遊中心點的時候，要注意中心點有兩種情況。

一個元素可以作為中心點，兩個元素也可以作為中心點。

三個元素是由一個元素為中心點擴散而來；四個元素為中心點是由兩個元素為中心點擴散而來。

代碼

動态規劃代碼

時間複雜度：O(n^2)
空間複雜度：O(n^2)

/*
 * @lc app=leetcode.cn id=647 lang=cpp
 *
 * [647] 回文子串
 */

// @lc code=start
class Solution {
public:
    int countSubstrings(string s) {
        int res = 0;//記錄回文子串的個數
        //定義和初始化dp數組
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        //周遊
        for(int i = s.size() - 1; i >= 0; i--)
        {
            for(int j = i; j < s.size(); j++)
            {
                if(s[i] == s[j])
                {
                    if(j - i <= 1)
                    {
                        res++;
                        dp[i][j] = true;
                    }
                    else if(dp[i + 1][j - 1])
                    {
                        res++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return res;
    }
};
// @lc code=end

雙指針思路

時間複雜度：O(n^2)
空間複雜度：O(1)

/*
 * @lc app=leetcode.cn id=647 lang=cpp
 *
 * [647] 回文子串
 */

// @lc code=start
class Solution {
private:
    int extend(string& s, int i, int j, int n)
    {
        int res = 0;
        while(i >= 0 && j < n && s[i] == s[j])
        {
            i--;
            j++;
            res++;
        }
        return res;
    }
public:
    int countSubstrings(string s) {
        int res = 0;
        for(int i = 0; i < s.size(); i++)
        {
            res += extend(s, i, i, s.size());//以一個點為中心
            res += extend(s, i, i + 1, s.size());//以兩個點為中心
        }
        return res;
    }
};
// @lc code=end

5.最長回文子串

題目

給你一個字元串

，找到

中最長的回文子串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：

輸入：s = "cbbd"
輸出："bb"

提示：

1 <= s.length <= 1000
s 僅由數字和英文字母組成

思路

雙指針的思路，和 647.回文子串的雙指針思路有點像。

代碼

/*
 * @lc app=leetcode.cn id=5 lang=cpp
 *
 * [5] 最長回文子串
 */

// @lc code=start
class Solution {
    private:
    //傳回最長回文子串
    int extend(string& s, int i, int j, int n)
    {
        int ex = 0;
        while(i >= 0 && j < n && s[i] == s[j])
        {
            i--;
            j++;
            ex++;
        }
        return ex;
    }
public:
    string longestPalindrome(string s) {
        //記錄最長回文子串的起始位置和終止位置，是前閉後閉區間
        int begin = 0;
        int end = 0;
        for(int i = 0; i < s.size(); i++)
        {
            //一個中心節點開始擴散
            int temp = extend(s, i, i, s.size());
            if(temp * 2 - 1 > end - begin + 1)
            {
                begin = i - (temp - 1);
                end = i + (temp - 1);
            }
            //兩個中心節點開始擴散
            temp = extend(s, i, i + 1, s.size());
            if(temp * 2 > end - begin + 1)
            {
                begin = i - temp + 1;
                end = i + temp;
            }
        }
        return string(s.begin() + begin, s.begin() + end + 1);
    }
};
// @lc code=end

516.最長回文子序列

代碼随想錄位址：https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html

這個題目說明初始化很重要。

題目

給你一個字元串

，找出其中最長的回文子序列，并傳回該序列的長度。

子序列定義為：不改變剩餘字元順序的情況下，删除某些字元或者不删除任何字元形成的一個序列。

示例 1：

輸入：s = "bbbab"
輸出：4
解釋：一個可能的最長回文子序列為 "bbbb" 。

示例 2：

輸入：s = "cbbd"
輸出：2
解釋：一個可能的最長回文子序列為 "bb" 。

提示：

1 <= s.length <= 1000
s 僅由小寫英文字母組成

思路

确定dp數組（dp table）以及下标的含義

dp[i] [j]：字元串s在[i, j]範圍内最長的回文子序列的長度為dp[i] [j]。

确定遞推公式

s[i] == s[j]，那麼dp[i] [j] = dp[i + 1] [j - 1] + 2;

如圖：

s[i] != s[j]：可以加入s[i]不加入s[j]，也可以加入s[j]不加入s[i]，看哪個更大。

dp[i] [j] = max(dp[i + 1] [j], dp[i] [j - 1]);

dp數組如何初始化

首先要考慮當i 和j 相同的情況，從遞推公式：dp[i] [j] = dp[i + 1] [j - 1] + 2; 可以看出遞推公式是計算不到 i 和j相同時候的情況。

是以需要手動初始化一下，當i與j相同，那麼dp[i] [j]一定是等于1的，即：一個字元的回文子序列長度就是1。

其他情況dp[i][j]初始為0就行，這樣遞推公式中dp[i] [j]才不會被初始值覆寫。

确定周遊順序

根據遞推公式，從下到上，從左到右。

舉例推導dp數組

草稿紙。

代碼

時間複雜度：O(n^2)
空間複雜度：O(n^2)

/*
 * @lc app=leetcode.cn id=516 lang=cpp
 *
 * [516] 最長回文子序列
 */

// @lc code=start
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //定義及初始化數組
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for(int i = 0; i < s.size(); i++)
            dp[i][i] = 1;
        //周遊
        //j一定要在i的右側
        for(int i = s.size() - 1; i >= 0 ; i--)
            for(int j = i + 1; j < s.size(); j++)
            {
                if(s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        return dp[0][s.size() - 1];
    }
};
// @lc code=end

動态規劃總結篇

代碼随想錄位址：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html

_49LeetCode代碼随想錄算法訓練營第四十九天-動态規劃 | 647.回文子串、516.最長回文子序列_49LeetCode代碼随想錄算法訓練營第四十九天-動态規劃 | 647.回文子串、516.最長回文子序列647.回文子串516.最長回文子序列動态規劃總結篇

_49LeetCode代碼随想錄算法訓練營第四十九天-動态規劃 | 647.回文子串、516.最長回文子序列

647.回文子串

題目

思路

動态規劃思路

雙指針思路

代碼

動态規劃代碼

雙指針思路

5.最長回文子串

題目

思路

代碼

516.最長回文子序列

題目

思路

代碼

動态規劃總結篇

繼續閱讀

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

HDU 1160 FatMouse's Speed （記錄路徑的最長上升子序列）

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

LeetCode OJ Binary Tree Right Side View

leetcode809

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希