680. Valid Palindrome II

ppxai

发布于 2023-11-18 08:30:54

1130

发布于 2023-11-18 08:30:54

文章被收录于专栏：皮皮星球

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:

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
    
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-04-14，如有侵权请联系 cloudcommunity@tencent.com 删除

input