【算法专题】动态规划之回文子串问题

动态规划6.0

• 动态规划 - - - 回文子串问题
• • 1. 回文子串
  • 2. 最长回文子串
  • 3. 分割回文串Ⅳ
  • 4. 分割回文串Ⅱ
  • 5. 最长回文子序列
  • 6. 让字符串成为回文串的最少插入次数

    动态规划 - - - 回文子串问题

    1. 回文子串

    题目链接 -> Leetcode -647.回文子串

    
    （图片来源网络，侵删）

    Leetcode -647.回文子串

    题目：给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

    回文字符串 是正着读和倒过来读一样的字符串。

    子字符串 是字符串中的由连续字符组成的一个序列。

    具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

    示例 1：

    输入：s = “abc”

    输出：3

    解释：三个回文子串 : “a”, “b”, “c”

    示例 2：

    输入：s = “aaa”

    输出：6

    解释：6个回文子串 : “a”, “a”, “a”, “aa”, “aa”, “aaa”

    提示：

    • 1 Leetcode -5.最长回文子串

      Leetcode -5.最长回文子串

      题目：给你一个字符串 s，找到 s 中最长的回文子串。

      如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

      示例 1：

      输入：s = “babad”

      输出：“bab”

      解释：“aba” 同样是符合题意的答案。

      示例 2：

      输入：s = “cbbd”

      输出：“bb”

      提示：

      • 1 retlen) { retlen = j - i + 1; begin = i; } } } return s.substr(begin, retlen); } };

        3. 分割回文串Ⅳ

        题目链接 -> Leetcode -1745.分割回文串Ⅳ

        Leetcode -1745.分割回文串Ⅳ

        题目：给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

        当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

        示例 1：

        输入：s = “abcbdd”

        输出：true

        解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。

        示例 2：

        输入：s = “bcbddxy”

        输出：false

        解释：s 没办法被分割成 3 个回文子字符串。

        提示：

        • 3 Leetcode -132.分割回文串Ⅱ

          Leetcode -132.分割回文串Ⅱ

          题目：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

          返回符合要求的 最少分割次数 。

          示例 1：

          输入：s = “aab”

          输出：1

          解释：只需一次分割就可将 s 分割成[“aa”, “b”] 这样两个回文子串。

          示例 2：

          输入：s = “a”

          输出：0

          示例 3：

          输入：s = “ab”

          输出：1

          提示：

          • 1 = 0; i--) { for(int j = i + 1; j