Home Computer Science Java Algorithm

891 · Valid Palindrome II - LintCode

# Description

Given a non-empty string  s , you may delete at most one character. Judge whether you can make it a palindrome.)

  1. The string will only contain lowercase characters.
  2. The maximum length of the string is 50000.

# Example

Example 1:

Input: s = "aba"
Output: true
Explanation: Originally a palindrome.

Example 2:

Input: s = "abca"
Output: true
Explanation: Delete 'b' or 'c'.

Example 3:

Input: s = "abc"
Output: false
Explanation: Deleting any letter can not make it a palindrome.

# Code

  • use two pointer
  • if the left char is not equal to the right, then break the while loop, and see if left + 1 or right - 1 is palidrome or not
public class Solution {
    /**
     * @param s: a string
     * @return: whether you can make s a palindrome by deleting at most one character
     */
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)){
                break;
            }
            left++;
            right--;
        }
   
    
        return isValid(s, left + 1, right) || isValid(s, left, right - 1);
    }
    private boolean isValid(String s, int left, int right) {
        while(left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}