ValidPalindromeII.py

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")

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;
}