Easy to Understand Python Solution

  • 6

    We can use the standard two-pointer approach that starts at the left and right of the string and move inwards. Whenever there is a mismatch, we can either exclude the character at the left or the right pointer. We then take the two remaining substrings and compare against its reversed and see if either one is a palindrome.

    - Yangshun

    class Solution(object):
        def validPalindrome(self, s):
            :type s: str
            :rtype: bool
            # Time: O(n)
            # Space: O(n)
            left, right = 0, len(s) - 1
            while left < right:
                if s[left] != s[right]:
                    one, two = s[left:right], s[left + 1:right + 1]
                    return one == one[::-1] or two == two[::-1]
                left, right = left + 1, right - 1
            return True

  • 0

    @yangshun it's not elegant when three double quote marks come together.

  • 1

    @mzchen I don't understand. Do you mean the docstring?

  • 2

    It`s really easy to understand. Thank you!

  • 0

    If I use reversed(one) instead of one[::-1] why does it give wrong answer?. Isn't it supposed to be the same thing?

  • 1

    reversed() returns a <listreverseiterator object> which is different from the list. You will have to cast it to a list: list(reversed(one)) instead, which is so long I prefer one[::-1].

  • 1

    @yangshun This is the best solution and is the most intuitive added to the bonus that it is also fast. I used your logic to implement a ruby solution:

    # @param {String} s
    # @return {Boolean}
    def valid_palindrome(s)
      l, r = 0, s.size - 1
      while l < r
        if s[l] != s[r]
          s1, s2 = s[l..r - 1], s[l + 1..r]
          return s1 == s1.reverse || s2 == s2.reverse
        l, r = l + 1, r - 1

    Hope it helps someone.

Log in to reply

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