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.
public class Solution {public bool ValidPalindrome(string s) {
return s == null || s.Length < 2 || IsValid(s, 0, s.Length - 1, false);
}
private bool IsValid(string s, int start, int end, bool hasDeleted)
{
if (start >= end) return true;
int i = start, j = end;
while (i < j)
{
if (s[i] != s[j])
{
if (hasDeleted) return false;
// we can try delete s[i] or s[j]
if (IsValid(s, i + 1, j, true) || IsValid(s, i, j - 1, true))
{
return true;
}
return false;
}
i++;
j--;
}
return true;
}
}
来源: http://www.bubuko.com/infodetail-2477771.html