Leetcode（java，python题解）:680.验证回文字符串II

Leetcode：680.验证回文字符串II

题目描述

Leetcode：https://leetcode-cn.com/problems/valid-palindrome-ii/

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: “aba”

输出: True

示例 2:

输入: “abca”

输出: True

解释: 你可以删除c字符。

注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

解题思路

使用双指针，遇到首尾不相等的先删除其中一个，再判断是否是回文

java代码

class Solution {
    public boolean validPalindrome(String s) {
        for(int i = 0, j = s.length() - 1; i < j; i++, j--){
            if(s.charAt(i) != s.charAt(j))
                return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
        }
        return true;
    }
    
    private boolean isPalindrome(String s, int i, int j){
        while(i < j){
            if(s.charAt(i++) != s.charAt(j--))
                return false;
        }
        return true;
    }
}
           

python代码

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if s == s[::-1]:
            return True
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] == s[j]:
                i, j = i + 1, j - 1
            else:
                return s[i + 1:j + 1] == s[i + 1:j + 1][-1::-1] or s[i:j] == s[i:j][-1::-1]
        return True
           

本文参考自CyC2018的GitHub项目更多内容访问如下链接

https://github.com/CyC2018/CS-Notes