Created
March 24, 2019 16:25
-
-
Save shixiaoyu/9ca84ae313bb812a699dae7bee0a2015 to your computer and use it in GitHub Desktop.
Valid Palindrome II version 2
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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