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

慈云数据 2024-05-30 技术支持 46 0

动态规划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
微信扫一扫加客服

微信扫一扫加客服

点击启动AI问答
Draggable Icon