##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/680.html

# 680. Valid Palindrome II (Easy)

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.

Companies:

Related Topics:
String

Similar Questions:

## Solution 1.

• class Solution {
public boolean validPalindrome(String s) {
int low = 0, high = s.length() - 1;
while (low < high) {
char c1 = s.charAt(low), c2 = s.charAt(high);
if (c1 == c2) {
low++;
high--;
} else {
boolean flag1 = true, flag2 = true;
for (int i = low, j = high - 1; i < j; i++, j--) {
char c3 = s.charAt(i), c4 = s.charAt(j);
if (c3 != c4) {
flag1 = false;
break;
}
}
for (int i = low + 1, j = high; i < j; i++, j--) {
char c3 = s.charAt(i), c4 = s.charAt(j);
if (c3 != c4) {
flag2 = false;
break;
}
}
return flag1 || flag2;
}
}
return true;
}
}

############

class Solution {
public boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return check(s, i + 1, j) || check(s, i, j - 1);
}
}
return true;
}

private boolean check(String s, int i, int j) {
for (; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}

• // OJ: https://leetcode.com/problems/valid-palindrome-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
bool validPalindrome(string s) {
int i = 0, j = s.size() - 1;
while (i < j && s[i] == s[j]) ++i, --j;
if (i >= j) return true;
auto valid = [&](int i, int j) {
while (i < j && s[i] == s[j]) ++i, --j;
return i >= j;
};
return valid(i + 1, j) || valid(i, j - 1);
}
};

• class Solution:
def validPalindrome(self, s: str) -> bool:
def check(i, j):
while i < j:
if s[i] != s[j]:
return False
i, j = i + 1, j - 1
return True

i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return check(i, j - 1) or check(i + 1, j)
i, j = i + 1, j - 1
return True

############

class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
isPalindrome = lambda s: s == s[::-1]
strPart = lambda s, x: s[:x] + s[x + 1:]
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return isPalindrome(strPart(s, left)) or isPalindrome(strPart(s, right))
left += 1
right -= 1
return True


• func validPalindrome(s string) bool {
check := func(i, j int) bool {
for ; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return check(i+1, j) || check(i, j-1)
}
}
return true
}

• function validPalindrome(s: string): boolean {
for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return (
isPalinddrome(s.slice(i, j)) ||
isPalinddrome(s.slice(i + 1, j + 1))
);
}
}
return true;
}

function isPalinddrome(s: string): boolean {
for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}


• /**
* @param {string} s
* @return {boolean}
*/
var validPalindrome = function (s) {
let check = function (i, j) {
for (; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
};
for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
if (s.charAt(i) != s.charAt(j)) {
return check(i + 1, j) || check(i, j - 1);
}
}
return true;
};