剑指 Offer II 019. 最多删除一个字符得到回文

题目链接

题目描述

解题思路

见18

代码

Python

def validPalindrome(s: str) -> bool:
    def isLegal(s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return False
        return True

    n = len(s)
    if n <= 1:
        return True
    left, right = 0, n - 1
    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
        else:
            return isLegal(s, left + 1, right) or isLegal(s, left, right - 1)
    return True

Go

func validPalindrome(s string) bool {
	n := len(s)
	if n <= 1 {
		return true
	}
	left, right := 0, n-1
	for {
		if left >= right {
			break
		}
		if s[left] == s[right] {
			left++
			right--
		} else {
			return isLegal(s, left+1, right) || isLegal(s, left, right-1)
		}
	}
	return true
}

func isLegal(s string, left int, right int) bool {
	for {
		if left >= right {
			break
		}
		if s[left] == s[right] {
			left++
			right--
		} else {
			return false
		}
	}
	return true
}