文章 220
评论 7
浏览 152716
680. Valid Palindrome II

680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

思路:

题目是让判断一个非空字符串在可以删除一个字符的情况下,是否是回文字符串。从贪心的角度考虑,可以发现如果一个字符串符合这种情况,一定是对于一个源串,去掉首或者尾的字符之后,剩下的字符串是回文的,因为字符串非空且只会为a-z,所以相比125题,不需要再去检验字符。

代码:

go:

func validPalindrome(s string) bool {
    i, j := 0, len(s) - 1
    for i < j {
        if s[i] != s[j] {
            return isValidPalindrome(s, i+1, j) || isValidPalindrome(s, i, j-1)
        }
        i++
        j--   
    }
    return true
}

func isValidPalindrome(s string, i, j int) bool {
    for i < j {
        if s[i] != s[j] {
            return false
        }
        i++
        j--
    }
    return true
    
}

标题:680. Valid Palindrome II
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2021/04/14/1618357972843.html

Nothing just happens, it's all part of a plan.

取消