Valid Palindrome II
给一个字符串问是否能通过删除最多一个字符后变成palindrome.
先写一个check回文的方法, 然后找到不对称的地方, 这时候已经知道要删除一个字符, 所以主要看删除后是否有可能变成回文即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: bool validPalindrome(string s) { int left = 0; int right = s.length() - 1; while(left < right) { if(s[left] != s[right]) { return check(s, left + 1, right) || check(s, left, right-1); } left++, right--; } return true; } bool check(string s, int i, int j) { while(i < j) { if(s[i] != s[j]) return false; i++; j--; } return true; } }; |