Leetcode solution 680: Valid Palindrome II
Leetcode solution 680: Valid Palindrome II
原文链接
https://blog.baozitraining.org/2019/03/leetcode-solution-680-valid-palindrome.html
Problem Statement
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: TrueExample 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.
Problem link
Video Tutorial
You can find the detailed video tutorial here
Thought Process
We should all be very familiar with how to determine if a string is a palindrome by keeping two pointers, one from beginning and one from the end of the string. The variation of this problem is to we can at most delete one character. Our thought process is the same to try two pointers. Let's use one example: "abbac", when we start two pointers, the first char 'a' and the last char 'c' are different. We might want to check if the previous of 'c' equals to 'a', we can have a chance OR the next after 'a' is a 'c', we can also have a chance. In this case, we return True since the previous of 'c' indeed is 'a' and the rest is simply a palindrome. However, what happens if we do have two choices? For example, "accac", the first 'a' and last 'c' are different, but we can choose either way, but it will result in different results. (i.e., "ccac" or "acca"), as long as one of the is a palindrome, we return True. Sounds familiar, yes, we can easily use recursion to achieve that. To make it better, we only need to recurse at most once since we are only allowed to delete at most one char.
Solutions
Implementation V1
// A quick implementation, a bit duplicate on checking on the palindrome part
public boolean validPalindromeFirstIteration(String s) {
// It says s is non-empty, the other is covered by normal case, so don't need this check
if (s == null || s.length() <= 2) {
return true;
}
int i = 0;
int j = s.length() - 1;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i++;
j--;
continue;
}
return isPalindromeHelper(s, i, j - 1) || isPalindromeHelper(s, i + 1, j);
}
return true;
}
public boolean isPalindromeHelper(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) == s.charAt(end)) {
start++;
end--;
continue;
}
return false;
}
return true;
}Implementation V2
// Need an intermediate Result class to return multiple values from a function
public class Result{
public boolean isPalindrome = false;
public int diffStartIndex = 0;
public int diffEndIndex = 0;
public Result(boolean isPalindrome, int diffStartIndex, int diffEndIndex) {
this.isPalindrome = isPalindrome;
this.diffStartIndex = diffStartIndex;
this.diffEndIndex = diffEndIndex;
}
}
public Result isPalindromeGenericHelper(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) == s.charAt(end)) {
start++;
end--;
continue;
}
return new Result(false, start, end);
}
return new Result(true, start, end);
}
public boolean validPalindrome(String s) {
// Just remember to add your VM params with -ea in your run configuration
assert s != null && s.length() > 0 : "Invalid input string s";
Result res = isPalindromeGenericHelper(s, 0, s.length()-1);
if (res.isPalindrome) {
return true;
}
return isPalindromeGenericHelper(s, res.diffStartIndex + 1, res.diffEndIndex).isPalindrome ||
isPalindromeGenericHelper(s, res.diffStartIndex, res.diffEndIndex - 1).isPalindrome;
}Time Complexity: O(N), N is the string length, worst case we traverse the string twice using recursion , O(N) + O(N) still equals O(N) Space Complexity: No additional space is needed (recursion function stack not included). Even counting function recursion stack, it's still O(1), which means constant space since you are bound to recurse only once
References
- A more clean solution