680. Validate palindrome string ⅱ

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Given a non-empty string s, at most one character is deleted. Determines whether it can become a palindrome string.

Example 1:

Input: s = “ABA” output: true

Example 2:

Input: s = “abca” Output: true Explanation: You can remove the C character.

Example 3:

Input: s = “ABC” Output: false

Their thinking

For judging palindrome strings, we can define the left and right Pointers, which initially point to the first and last character of the string respectively, and judge whether the left and right Pointers point to the same character each time. If not, it is not a palindrome string. If they are the same, move the left and right Pointers one bit to the middle until the left and right Pointers meet, and the string is a palindrome string.

In this problem, according to this idea, when we encounter two characters that do not match, we can try to delete both characters once and traverse the remaining string to see if it can form a palindrome string. If it still fails, it means that deleting a character does not make the string become a palindrome

code

class Solution {
    public boolean validPalindrome(String s) {

        int l=0,n=s.length(),r=n-1;
        while(l<r)
        {
            if(s.charAt(l)! =s.charAt(r)) {return toVlidPalindrome(s,l+1,r)||toVlidPalindrome(s,l,r-1);

            }
                r--;
                l++;
        }
        return true;
    }
    public boolean toVlidPalindrome(String s,int l,int r) {
        while(l<r)
        {
            if(s.charAt(l)! =s.charAt(r))return false;
            l++;
            r--;
        }
        return true; }}Copy the code

Time complexity: O(n), where n is the length of the string. The time complexity to determine whether the entire string is a palindrome string is O(n), and the time complexity to determine whether two substrings are palindrome strings when different characters are encountered is also O(n).

Space complexity: O(1). Only a limited amount of constant space needs to be maintained.

680. Validate palindrome string ⅱ