Skip to content

Instantly share code, notes, and snippets.

@c02y
Created May 14, 2020 19:59
Show Gist options
  • Save c02y/cb758d663750a4c227d3a26c70f275c0 to your computer and use it in GitHub Desktop.
Save c02y/cb758d663750a4c227d3a26c70f275c0 to your computer and use it in GitHub Desktop.
ValidPalindromeII.py
# 680. Valid Palindrome II (Easy)
# https://leetcode-cn.com/problems/valid-palindrome-ii/description/
class Solution:
def validPalindrome(self, s):
if s == s[::-1]:
return True
l, r = 0, len(s) - 1
while l < r:
if s[l] == s[r]:
l, r = l + 1, r - 1
else:
# NOTE: l:r does not include r
a = s[l + 1:r + 1]
b = s[l:r]
return a == a[::-1] or b == b[::-1]
if __name__ == '__main__':
mystring = "abcdedcxba"
if Solution().validPalindrome(mystring):
print("True")
else:
print("False")
@c02y
Copy link
Author

c02y commented May 14, 2020

Cpp version:

// 680. Valid Palindrome II (Easy)
// https://leetcode-cn.com/problems/valid-palindrome-ii/description/
#include <iostream>

class Solution {
public:
	bool validPalindrome(std::string s) {
		int i = 0, j = s.length() - 1;

		std::string rev_s = rev_string(s);
		if (rev_s == s)
			return true;

		while (i < j) {
			if (s[i] == s[j]) {
				i++;
				j--;
			} else {
				// NOTE: substr(startIndex, length), length=end-startIndex
				std::string a = s.substr(i + 1, j - i);
				std::string b = s.substr(i, j - i);
				return (a == rev_string(a) || b == rev_string(b)) ? true : false;
			}
		}
		return false;
	}

	std::string rev_string(std::string s)
	{
		int len = s.length();
		std::string rev_s(s);
		for (int i = 0; i < len / 2; i++) {
			std::swap(rev_s[i], rev_s[len - i - 1]);
		}
		return rev_s;
	}

};

int main()
{
	std::string data("abcdedcxba");

	Solution solu;
	std::cout << (solu.validPalindrome(data) ? "YES" : "NO") << std::endl;

	return 0;
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment