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:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
class Solution { public boolean validPalindrome(String s) { if (s == null || s.length() < 2) { return true; } int left = 0; int right = s.length() - 1; while ( left < right && s.charAt(left) == s.charAt(right)) { left++; right--; } if (left >= right) { return true; } if (isPalin(s, left + 1, right) || isPalin(s, left, right - 1)) { return true; } return false; } private boolean isPalin(String s, int left, int right) { while (left < right) { if (s.charAt(left) == s.charAt(right)) { left++; right--; } else { break; } } return left >= right; } }
No comments:
Post a Comment