680.Valid_Palindrome_II.md

680. Valid Palindrome II 难度 简单

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false
 

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.

相关企业 半年内半年 ~ 1年1年 ~ 2年 Facebook|162 谷歌 Google|2 苹果 Apple|2 亚马逊 Amazon|2 甲骨文 Oracle|2

相关标签 Greedy Two Pointers String

相似题目 Valid Palindrome 简单

thought

• firstly do palindrome
• then modify base on it
  • when first time meet not-palindrome don't return false,
  • check one more time after removing one char (left++ or right--)

basic version

• but some code repeat

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null || s.length() == 0){
            return false;
        }

        int left = 0;
        int right = s.length() - 1;
        while(left < right){
            while (left < s.length() && !this.isValid(s.charAt(left)) ){
                left ++;
            }
            if (left == s.length()){
                return true; // all char are invalid and this case is palindrome
            }

            while (right > 0 && !this.isValid(s.charAt(right)) ){
                right --;
            }

            if (Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))){
                left ++;
                right --;
            }else{
                return this.isSubPalindrome(s, left+1, right) || this.isSubPalindrome(s, left, right-1);
            }
        }
        
        return left >= right;
    }

    public boolean isSubPalindrome(String s, int left, int right){
        while(left < right){
            while (left < s.length() && !this.isValid(s.charAt(left)) ){
                left ++;
            }
            if (left == s.length()){
                return true; // all char are invalid and this case is palindrome
            }

            while (right > 0 && !this.isValid(s.charAt(right)) ){
                right --;
            }

            if (Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))){
                left ++;
                right --;
            }else{
                return false;
            }
        }

        return left >= right;
    }

    public boolean isValid(char c){
        return Character.isDigit(c) || Character.isLetter(c);
    }
}

better

• use sub function to replace repeated code

class Solution {
    public boolean validPalindrome(String s) {
        if (s == null || s.length() == 0){
            return false;
        }

        int left = 0;
        int right = s.length() - 1;
        LeftRightPair pr = findDifference(s, left, right);
        if (pr.l >= pr.r){
            return true;
        }else{
            return this.isSubPalindrome(s, pr.l+1, pr.r) || this.isSubPalindrome(s, pr.l, pr.r-1);
        }

        
    }

    private LeftRightPair findDifference(String s, int left, int right){
        while(left < right){
            while (left < s.length() && !this.isValid(s.charAt(left)) ){
                left ++;
            }
            if (left == s.length()){
                return new LeftRightPair(left, right); // all char are invalid and this case is palindrome
            }

            while (right > 0 && !this.isValid(s.charAt(right)) ){
                right --;
            }

            if (Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))){
                left ++;
                right --;
            }else{
                return new LeftRightPair(left, right);
            }
        }
        return new LeftRightPair(left, right);
    }

    private boolean isSubPalindrome(String s, int left, int right){
        LeftRightPair pr = findDifference(s, left, right);
        if (pr.l >= pr.r){
            return true;
        }
        return false;
    }

    public boolean isValid(char c){
        return Character.isDigit(c) || Character.isLetter(c);
    }
}

class LeftRightPair{
    int l;
    int r;

    public LeftRightPair(int l, int r){
        this.l = l;
        this.r = r;
    }
}

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if not s:
            return False

        left, right = self.findDifference(s, 0, len(s) - 1)
        if left >= right:
            return True
        else:
            return self.isSubPalindrome(s, left + 1, right) or self.isSubPalindrome(s, left, right - 1)

    def isSubPalindrome(self, s, l, r):
        l, r = self.findDifference(s, l, r)
        return l >= r


        
    def findDifference(self, s, l, r):
        while l < r:
            while l < len(s) and not self.isValid(s[l]):
                l += 1
            if l == len(s):
                return l, r

            while r > 0 and not self.isValid(s[r]):
                r -= 1

            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                return l, r
        return l, r

    def isValid(self, c):
        return c.isalpha() or c.isdigit()