Algorithm
Problem Name: 680. Valid Palindrome II
Problem Link: https://leetcode.com/problems/valid-palindrome-ii/
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = "aba" Output: true
Example 2:
Input: s = "abca" Output: true Explanation: You could delete the character 'c'.
Example 3:
Input: s = "abc" Output: false
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool validPalindrome(string s) {
int i = 0, j = s.size() - 1;
while(i < = j && s[i] == s[j]) i++, j--;
return i > j || isValid(s.substr(i, j - i)) || isValid(s.substr(i + 1, j - i));
}
bool isValid(string s){
int i = 0, j = s.size() - 1;
while(i < = j && s[i] == s[j]) i++, j--;
return i > j;
}
};
Input
s = "aba"
Output
true
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean validPalindrome(String s) {
return validPalindromeHelper(s, false);
}
private boolean validPalindromeHelper(String s, boolean deleted) {
int startIdx = 0;
int endIdx = s.length() - 1;
while (startIdx < endIdx) {
if (s.charAt(startIdx) != s.charAt(endIdx)) {
if (deleted) {
return false;
}
return validPalindromeHelper(s.substring(0, startIdx) + s.substring(startIdx + 1), true) ||
validPalindromeHelper(s.substring(0, endIdx) + s.substring(endIdx + 1), true);
}
startIdx++;
endIdx--;
}
return true;
}
}
Input
s = "aba"
Output
true
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const validPalindrome = function(s) {
let start = 0;
let end = s.length - 1;
const isPalindrome = function(start, end, removed) {
while (start < = end) {
if (s[start] !== s[end]) {
if (removed) {
return false;
}
return (
isPalindrome(start + 1, end, true) ||
isPalindrome(start, end - 1, true)
);
}
start++;
end--;
}
return true;
};
return isPalindrome(start, end, false);
};
Input
s = "abca"
Output
true
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
memo = {}
def dfs(l, r, cnt):
if (l, r, cnt) in memo:
return memo[(l, r, cnt)]
if l >= r:
return True
elif s[l] != s[r]:
cnt += 1
if cnt > 1:
memo[(l, r, cnt)] = False
return False
elif (s[l + 1] == s[r] and dfs(l + 1, r, cnt + 1)) or (s[l] == s[r - 1] and dfs(l, r - 1, cnt + 1)):
memo[(l, r, cnt)] = True
return True
else:
memo[(l, r, cnt)] = False
return False
else:
memo[(l, r, cnt)] = dfs(l + 1, r - 1, cnt)
return memo[(l, r, cnt)]
return dfs(0, len(s) - 1, 0)
Input
s = "abca"
Output
true
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0680_ValidPalindromeII
{
public bool ValidPalindrome(string s)
{
for (int i = 0; i < s.Length / 2; i++)
{
var j = s.Length - 1 - i;
if (s[i] != s[j])
return ValidPalindrome(s, i, j - 1) || ValidPalindrome(s, i + 1, j);
}
return true;
}
private bool ValidPalindrome(string s, int i, int j)
{
for (int k = i; k < = i + (j - i) / 2; k++)
if (s[k] != s[j - k + i]) return false;
return true;
}
}
}
Input
s = "abc"
Output
false