回文串问题

算法双指针

发布日期: 2023-06-15

更新日期: 2023-06-17

文章字数: 239

阅读时长: 1 分

阅读次数:

什么是回文串

回文串通俗来说一个字符串从前往后读和从后往前读是相同的，这样的字符串就叫做字符串。判断回文串，一般的做法就是定义两个指针，一前一后，分别往中心位置遍历，如果在遍历的过程中，每次比较的前后字符都相等，则为回文串

例题

给定一个字符串 s ，验证 s 是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。将空字符串定义为有效的回文串

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

分析：这一题是最基础的回文串问题，就是判断这个字符串是不是回文，只不过这里要排除一些特殊字符的情况
代码如下：

func isValid(b byte) bool {
 return  (b >= 'A' && b <= 'Z') || (b >= 'a' && b <= 'z') || (b >= '0' && b <= '9')
}
// 双指针法
func isPalindrome3(s string) bool {
 s = strings.ToLower(s) // 全部转成小写
 left, right := 0, len(s) - 1
 for left < right {
     b1 := s[left]
     b2 := s[right]
     if !isValid(b1)  {
         left++
         continue
     }
     if !isValid(b2) {
         right--
         continue
     }
     if b1 != b2 {
         return false
     }
     left++
     right--
 }
 return true
}

题目：给定一个非空字符串 s，请判断如果最多从字符串中删除一个字符能否得到一个回文字符串。
```
输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符
```
分析：这一题是在上一题的基础之上，做了一些变形。不是直接判断是不是回文串，让我们去考虑需要删除一个字符后，再来判断是不是回文串。有了上一题判断回文串的方法，我们只需要关注怎么去删除一个字符。我们可能想，尝试从头到尾逐个删除每一个字符的思路去判断，但是这样的话，时间复杂度会比较高。这里采取的方式，还是双指针，一头一尾，逐个判断，当遇到不相同的字符的时候，这里很关键。就是尝试两边都去删除着不同的字符，然后分别去判断，只有其中一个满足相等，那么整体就是回文的情况。
代码如下：
```
func validPalindrome(s string) bool {
 left, right := 0, len(s) -1
 for left < right {
     if s[left] == s[right] {
         left++
         right--
     }else {
         newLeft :=  left + 1
         newRight := right - 1
         b1 := delOneByteValidPalindrome(s, newLeft, right) //
         b2 := delOneByteValidPalindrome(s, left, newRight)
         return b1 || b2
     }
 }
 return true
}
func delOneByteValidPalindrome(s string, left, right int) bool {
 for left < right {
     if s[left] != s[right] {
         return false
     }
     left++
     right--
 }
 return true
}
```
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
```
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
```

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

分析：这一题是统计字符串中的回文子串个数，一般就是求出字符串的所有子串，然后逐个去判断是否是回文。这里主要讲一下动态规划的思路，觉得这个思路很巧妙。定义一个数组DP[], 一个一维数组很难去确定dp[i] 与dp[i-1], dp[i+1] 的关系。所以这里尝试使用二维数组dp[i][j], 表达区间范围【i, j】是否是回文子串。然后我们分析一下回文字符的情况，已知下标i， j， i < j, 如果s[i] != s[j] , 一定不是回文子串, 如果s[i] == s[j],不能就认为是回文子串，当i，j中间只有一个字符的情况，是回文字符，如果中间有两个字符的时候，并且这两个字符相等，也是回文字符。当中间的字符大于2个的时候，只需要去判断【i + 1, j - 1】是否是回文，综合上述，就可以确定递推关系了。

if s[i] == s[j] {
    if j - i <= 1 { // 情况一 和 情况二
        ans++;
        dp[i][j] = true;
    } else if dp[i + 1][j - 1] { // 情况三
        ans++;
        dp[i][j] = true;
    }
}

代码如下：

n := len(s)
    count := 0
    var dp  [1001][1001]bool
    for ii := n - 1; ii >= 0; ii-- {
        for jj := ii; jj < n; jj++ {
            if s[ii] == s[jj] && (jj - ii <= 1 || dp[ii + 1][jj - 1]) {
                count++
                dp[ii][jj] = true
            }
        }
    }
    return count