回文串 leetcode

柔情只为你懂 2022-12-30 13:58 92阅读 0赞

1. [125. 验证回文串][125.]

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

**说明：**本题中，我们将空字符串定义为有效的回文串。

**示例 1:**

输入: "A man, a plan, a canal: Panama"
    输出: true

**示例 2:**

输入: "race a car"
    输出: false

解法1:

class Solution:
        def isPalindrome(self, s: str) -> bool:
            ss = [item.lower() for item in s  if 'a' <= item.lower() <= 'z' or '0' <= item.lower() <= '9']
            return ''.join(ss[::-1]) == ''.join(ss)

解法2:  双指针， 简单题 必有 对应的 中等题 难题， 做每一道简单题 必须看 题解，

class Solution:
        def isPalindrome(self, s: str) -> bool:
            # 双指针, 左右指针
            s = "".join(ch.lower() for ch in s if ch.isalnum())
            left, right = 0, len(s)-1
            # 判断一段文本 是否 回文串
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

2. [5. 最长回文子串][5.]

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。

**示例 1：**

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

**示例 2：**

输入: "cbbd"
    输出: "bb"

解法1: 官方 动态规划

class Solution:
        def longestPalindrome(self, s: str) -> str:
            # 动态规划，
            # 方程 j-i>=2, P(i, j)=P(i+1,j-1)^(Si==Sj)
            # j==i(一个字母) -> 必是， j=i+1(两个字母), Si==Sj+1
            s_len = len(s)
            dp = [[False]*s_len for _ in range(s_len)]
            ans=""
            # 先遍历长度, j表示长度
            for lg in range(s_len):
                # 遍历起始位置
                for i in range(s_len): # dp[i][j] 表示 从i～j是回文串
                    j = i + lg  # 看i~j的区间 是否是回文串
                    if j >= s_len:
                        break
                    if lg==0:
                        dp[i][j]=True
                    elif lg==1:
                        dp[i][j] = (s[i]==s[j])
                    # elif lg >= 2:
                    else:
                        dp[i][j] = (dp[i+1][j-1] and s[i]==s[j])
                    if dp[i][j] and lg+1 > len(ans):
                        ans = s[i:j+1]
            return ans

[125.]: https://leetcode-cn.com/problems/valid-palindrome/
[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/