C#LeetCode刷题之#680-验证回文字符串 Ⅱ​​​​​​​（Valid Palindrome II）

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Input: “aba”

Output: True

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 Program {

public static void Main(string[] args) {
var s = "abca";

var res = ValidPalindrome(s);
Console.WriteLine(res);

s = "Iori's Blog!";

res = ValidPalindrome2(s);
Console.WriteLine(res);

}

private static bool ValidPalindrome(string s) {
//暴力解法，超时未AC
if(IsPalindrome(s)) return true;
for(int i = 0; i < s.Length; i++) {
var substring = s.Remove(i, 1);
if(IsPalindrome(substring)) return true;
}
return false;
}

private static bool IsPalindrome(string s) {
//前后双指针法
var i = 0;
var j = s.Length - 1;
while(i < j) {
if(s[i] != s[j]) return false;
i++;
j--;
}
return true;
}

public static bool ValidPalindrome2(String s) {
var i = -1;
var j = s.Length;
while(++i < --j)
//不相同时，并不代表就不是回文了，因为有删除一个字符的机会
//但我们不知道往前删除还是往后删除
//所以我们前后各判定一次
if(s[i] != s[j])
return IsPalindrome2(s, i, j - 1) || IsPalindrome2(s, i + 1, j);
return true;
}

private static bool IsPalindrome2(String s, int i, int j) {
while(i < j) if(s[i++] != s[j--]) return false;
return true;
}

}```

```True
False```

(1)