680.Valid-Palindrome-II.md

680. Valid Palindrome II

---

题目地址

https://leetcode.com/problems/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:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

代码

Approach #1 Greedy

class Solution {
  public boolean validPalindrome(String s) {
    int n = s.length();
		for (int i = 0; i < n / 2; i++) {
      if (s.charAt(i) != s.charAt(n - 1 - i)) {
        int j = s.length() - 1 - i;
        return (isPalindromeRange(s, i + 1, j)
               || isPalindromeRange(s, i, j - 1));
      }
    }
  }
  
  private boolean isPalindromeRange(String s, int i, int j) {
    for (int k = i; k <= i + (j - i) / 2; k++) {
      if (s.charAt(k) != s.charAt(j - k + i))	{
        return false;
      }
    }
    return true;
  }
  
}

Approach #2

class Solution {
  public boolean validPlindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
      if (s.charAt(i) != s.charAt(j)) {
        int i1 = i, j1 = j - 1;
        int i2 = i + 1, j2 = j;
        while (i1 < j1 && s.charAt(i1) == s.charAt(j1)) {
          i1++;
          j1--;
        }
        while (i2 < j2 && s.charAt(i2) == s.charAt(j2)) {
          i2++;
          j2--;
        }
        
        return i1 >= j1 || i2 >= j2;
      }
    }
    return true;
  }
}