Leetcode-680-验证回文串II

Leecode-680-Valid Palindrome II

思路：双指针

题目描述

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

输入: "aba"
输出: True

输入: "abca"
输出: True
解释: 你可以删除c字符。

Solution：

• 本题基于Leetcode–125题基础上增加了可以删除一个字母达到回文串的效果

• 首先我们来看一下如果判断回文串的代码

public boolean isPalindrime(String s,int i,int j){
    while (i < j){
        // 如果两个指针不相等
        if (s.charAt(i) != s.charAt(j)){
            return false;
        }else {
            // 相等的话就各移动一位
            i++;
            j--;
        }
    }
    // 全都满足返回true
    return true;
}

• 思路：两次回文串判断
  • 第一次：如上代码，判断一个字符串是不是回文串
  • 第二次：如果不是，给你一次机会（这里指的机会是：删除一个字母）
    • （删除的含义：递归判断左指针+1 到右指针 或者 左指针到右指针-1）这两者其一是不是回文串。

Java

Solution :

class Solution {
    // 第二次判断
    public boolean validPalindrome(String s) {
        if(s == null||s.equals("")){
            return false;
        }

        int left  = 0;
        int right = s.length() - 1;

        while (left < right){
            // 如果当前左右指针不相等
            if (s.charAt(left) != s.charAt(right)){
                // 判断左指针+1 到右指针 或者 左指针到右指针-1
                // 两者其一是不是回文串
                return isPalindrime(s,left + 1,right)||isPalindrime(s,left,right - 1);
            }
            // 是的话就各移动一位
            left++;
            right--;
        }
        return true;
    }


    // 第一次判断
    public boolean isPalindrime(String s,int i,int j){
        while (i < j){
            // 如果两个指针不相等
            if (s.charAt(i) != s.charAt(j)){
                return false;
            }else {
                // 相等的话就各移动一位
                i++;
                j--;
            }
        }
        // 全都满足返回true
        return true;
    }
}

Python

Solution :

打赏