LC-0680 Easy LeetCode

680. Valid Palindrome II

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 43% Topics: Two Pointers, String, Greedy

Reading material

Two Pointers 9 min Strings 12 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        def validPalindrome(s, left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left, right = left+1, right-1
            return True

        left, right = 0, len(s)-1
        while left < right:
            if s[left] != s[right]:
                return validPalindrome(s, left, right-1) or validPalindrome(s, left+1, right)
            left, right = left+1, right-1
        return True

Solution from kamyu104/LeetCode-Solutions · MIT