[LeetCode]Valid Palindrome II

只删除一个字符看是否可以变为回文。首先我们如何判断一个string是回文呢，当然是双指针头尾扫。如果当前首尾指针指向的字符相同，那么目前我们扫过的区域是符合要求的；当我们碰到首尾指针指向不同字符的情况时，很明显，代表我们需要删掉这两字符的其中一个了。删掉哪个我们并不确定，所以我们两种情况都考虑。假设两个指针分别为i, j，并且s[i] != s[j]，那么我们就需要分别check s[i + 1, j]，s[i, j - 1]是否分别为回文，如果这两个至少有一个是回文，也就是表明删掉一个字符可以使原字符变为回文。常数空间，时间复杂度O(n)，最多扫两遍字符串，代码如下：

	class Solution {
	public:
	bool validPalindrome(string s) {
	int len = s.size(), i = 0, j = len - 1;
	while(i < j)
	{
	if(s[i] != s[j])
	return isPalin(s.substr(i, j - i)) || isPalin(s.substr(i + 1, j - i));
	++i;
	--j;
	}
	return true;
	}
	private:
	bool isPalin(string s)
	{
	int len = s.size(), i = 0, j = len - 1;
	while(i < j)
	{
	if(s[i++] != s[j--])
	return false;
	}
	return true;
	}
	};

view raw Valid Palindrome II.cpp hosted with ❤ by GitHub