Wednesday, February 20, 2019

Leetcode 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:
  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Code (Java):
class Solution {
    public boolean validPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }
        
        int left = 0;
        int right = s.length() - 1;
        
        while  ( left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        
        if (left >= right) {
            return true;
        }
            
        if (isPalin(s, left + 1, right) || 
            isPalin(s, left, right - 1)) {
                return true;
        }
        
        return false;
    }
    
    private boolean isPalin(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                break;
            }
        }
        
        return left >= right;
    }
}

No comments:

Post a Comment