Skip to content

Instantly share code, notes, and snippets.

@shixiaoyu
Created March 24, 2019 16:25
Show Gist options
  • Save shixiaoyu/9ca84ae313bb812a699dae7bee0a2015 to your computer and use it in GitHub Desktop.
Save shixiaoyu/9ca84ae313bb812a699dae7bee0a2015 to your computer and use it in GitHub Desktop.
Valid Palindrome II version 2
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment