5、回文子串

一、定义

回文字符串

• 是正着读和倒过来读一样的字符串。
• 和奇数数量有关
• 倒叙挺好用的
• 双指针和动态规划是一般的解题方法

二、验证回文串

125 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

思路：

我们可以根据回文串的定义使用双指针的方式，前后两个指针分别指向字符的前后，前后两个指针的字符串一致即可

其他条件小写字符，移除非字母数字的字符

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left <= right:
            if not s[left].isdigit() and not s[left].isalpha():
                left += 1
                continue
            if not s[right].isdigit() and not s[right].isalpha():
                right -= 1
                continue

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1
        return True

680. 验证回文串 II

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"
输出：false

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

思路：

最多删除一个字符，假如一个字符本身就是回文串，那么它的直接倒叙就是它本身，如果字符串的倒叙和字符串本身删除第一个不相同的字符不相同，那么它则不是回文串

class Solution:
    def validPalindrome(self, s: str) -> bool:
        s1 = s[::-1]
        if s == s1:
            return True
        for i in range(len(s)):
            if s[i] != s1[i]:
                new1 = s[:i] + s[i + 1 :]
                new2 = s1[:i] + s1[i + 1 :]
                return new1 == new1[::-1] or new2 == new2[::-1]
        return False

回文子串和子序列问题

5. 最长回文子串

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

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路：

回文子串问题一般的解题思路都是动态规划或者是双指针

关于这个题我们首先使用动态规划的思路处理

如果s[i]==s[j]这个时候我们需要看i和j之间的距离，i和j距离大于1，那我们需要判断dp[i+1][j-1]之间是不是回文串就可以，假如i和j之间的距离小于1，就比如这样aa,那么它一定是回文串。我们这里进行一个曲线救国，就是先找到所有的回文串，然后再找最长的。

我们使用动规五部曲进行处理

• 确定dp数据含义，表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dpi][j]为true，否则为false。

• 递推公式

  • 我们判断的条件都是在i==j的情况下
  • j-i>1:s[i] == s[j] and s[i+1][j-1]
  • j-i<=1: s[i] == s[j]

• 初始化：一开始i==j的时候初始化为True,其他情况都初始化为False。可以先不初始化。

• 遍历顺序：所以i是从下到上，j是从左到右

  

• 打印dp

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = 0
        max_length = 0
        n = len(s)
        dp = [[False] * n for _ in range(n )]

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if j - i > 1:
                    dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j]

                if dp[i][j] and j - i + 1 > max_length:
                    max_length = max(max_length, j - i + 1)
                    start = i
        return s[start : start + max_length]

647. 回文子串

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

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

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

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

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

这个题是不是和上一题是一致的

连思路都是一样的

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]

        result = 0
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if j - i > 1:
                    dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j]
                if dp[i][j]:
                    result += 1
        return result

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

思路：

• 确定dp数组含义：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]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列
  • 即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
• 初始化
  • 当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
• 确定遍历顺序

clclass Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1

        for i in range(n - 1, -1, -1):
            # 当i=j时这时dp[i][j]的长度已经确定了，所以要从i+1开始算起
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return max([max(i) for i in dp])

构造回文串

1400. 构造 K 个回文字符串

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

示例 1：

输入：s = "annabelle", k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

示例 2：

输入：s = "leetcode", k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。

示例 3：

输入：s = "true", k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

示例 4：

输入：s = "yzyzyzyzyzyzyzy", k = 2
输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。

示例 5：

输入：s = "cr", k = 7
输出：false
解释：我们没有足够的字符去构造 7 个回文串。

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        from collections import Counter
        counter = Counter(s)
        result = 0
        for key, value in counter.items():
            if value %2 ==1: 
                result +=1
        return result <= k