680.Valid-Palindrome-II

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:
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;
}
}