3.3 回文字符串

回文是一类特殊字符串: 从头到尾读取和从尾到头读取所获取的结果相同.

3.3.1 问题18: 有效的回文

LCR 018. 验证回文串

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

本题中，将空字符串定义为有效的 回文串 。

示例 1:

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

示例 2:

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

提示：

• 1 <= s.length <= 2 * 105
• 字符串 s 由 ASCII 字符组成

3.3.1.1 分析

使用双指针从两边开始反向移动, 判断指针指向的字符是否相同, 跳过非字母/数字的字符.

不考虑大小写, 则可以将字母都转换成小写.

3.3.1.2 题解

func isPalindrome(s string) bool {
	// 边界
	if len(s) == 0 {
		return true
	}

	// 双指针
	left, right := 0, len(s)-1
	for left < right {
		lc := rune(s[left])
		rc := rune(s[right])

		if !isLetterOrDigigt(lc) {
			left++
			continue
		}
		if !isLetterOrDigigt(rc) {
			right--
			continue
		}
		// to lower case
		lc = unicode.ToLower(lc)
		rc = unicode.ToLower(rc)
		if lc != rc {
			return false
		}

		left++
		right--
	}

	return true
}

func isLetterOrDigigt(c rune) bool {
	return unicode.IsLetter(c) || unicode.IsDigit(c)
}

3.3.2 问题19: 最多删除一个字符得到回文

LCR 019. 验证回文串 II

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1:

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

示例 2:

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

示例 3:

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

提示:

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

3.3.2.1 分析

使用双指针从两端开始, 比较字符是否相同.

不相同的话, 则分别删除两个字符后再判断是否是回文串.

3.3.2.2 题解

func validPalindrome(s string) bool {
	left, right := 0, len(s)-1
	for left < len(s)/2 {
		if s[left] != s[right] {
			break
		}
		left++
		right--
	}

	return left == len(s)/2 || isPalindrome19(s, left+1, right) || isPalindrome19(s, left, right-1)
}

func isPalindrome19(s string, left, right int) bool {
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

3.3.3 问题20: 回文子串的个数

LCR 020. 回文子串

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

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

示例 1：

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

示例 2：

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

提示：

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

3.3.3.1 分析

遍历字符串, 对于一个字符 s[i], 以其为对称中心则有:

• 若为奇数回文: 对称中心是自身 s[i]
• 若为偶数回文: 对称中心是 [s[i], s[i+1]]

从对称中心向两边同时扩展, 若两边的字符相同的为回文子串.

3.3.3.2 题解

使用了两重循环, 时间复杂度: O($n^2$)

func countSubstrings(s string) int {
    count := 0
    // 边界
    if len(s) == 0 {
       return count
    }

    // 扫描 s
    for i := range s {
       // 奇数长回文
       count += countPalindrome(s, i, i)
       // 偶数长回文
       count += countPalindrome(s, i, i+1)
    }

    return count
}

func countPalindrome(s string, c1, c2 int) int {
    count := 0
    left, right := c1, c2
    // 从中心向两边扩展
    for left >= 0 && right < len(s) {
       if s[left] != s[right] {
          return count
       }
       count++
       left--
       right++
    }
    return count
}

Reference

1. 剑指Offer（专项突破版）