Simple python solution

  • 3

    Whenever there is a mismatch when checking for palindrome, we try deleting either one of the two characters involved in the mismatch and see if isPalindrome succeeds. To make sure, we don’t delete more than 1 character, we also maintain the delCount.

        def isPalindrome(self, s, start, end, delCount):
            if delCount > 1:
                return False
            while start < end:
                if s[start] != s[end]:
                start += 1
                end -= 1
            if (start == end) or (start == end+1):
                return True
            return any([self.isPalindrome(s, start+1, end, delCount+1), self.isPalindrome(s, start, end-1, delCount+1)])
        def validPalindrome(self, s):
            return self.isPalindrome(s, 0, len(s)-1, 0)

  • 0

    nice and clever. I guess it is O(n) time where it checks each character only once and also despite recursion it is O(1) because recursion depth can not exceed 2. Nice one!

  • 0

    @sha256pki Thanks :)

  • 0

    Your any([x, y]) is rather strange and inefficient... why not just x or y?

  • 0

    @StefanPochmann still learning the ropes :), thanks for pointing this out.

  • 0

    Very clever!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.