Python in-place two-pointer solution.


  • 31
    C
    def isPalindrome(self, s):
        l, r = 0, len(s)-1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l <r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l +=1; r -= 1
        return True

  • 0

    while l < r and not s[l].isalnum():
    l += 1
    while l <r and not s[r].isalnum():
    r -= 1
    What is the meaning of 4 line above?


  • 1
    J

    @Zura if it is a space or not alphanumeric, skip


  • 0
    X

    it works, but looks weird with two while loops of 'i < j'; could be better, but i don't know how to improve :P


  • 0
    S

    It seems one can replace the nested while loops with while and continue

    class Solution(object):
        def isPalindrome(self, s):
            """
            :type s: str
            :rtype: bool
            """
            l, r = 0, len(s) - 1
            while l < r:
                if not s[l].isalnum():
                    l += 1
                    continue
                if not s[r].isalnum():
                    r -= 1
                    continue
                if s[l].lower() == s[r].lower():
                    l += 1
                    r -= 1
                else:
                    return False
            return True
    
    if __name__ == '__main__':
        print Solution().isPalindrome("A man, a plan, a canal: Panama")
    

  • 1
    S
            l, r = 0, len(s) - 1
            while l < r:
                if not s[l].isalnum():
                    l += 1
                elif not s[r].isalnum():
                    r -= 1
                elif s[l].lower() != s[r].lower():
                    return False
                else:
                    l += 1; r -= 1
            return True
    

    hmm i have no idea why you need that while l < r in each condition


  • 0
    M

    @caikehe Hi, my solution does not work for a string with newline characters. So I tried yours, but that also does not work. Example,
    "A man
    a plan"
    Could you please help me? Thanks


  • 0
    K
    def isPalindrome(self, s):
          import re         
    
          if len(s) < 2 : 
                return True   
          
          s  = re.sub(r'\W+', '', s).replace(' ','').lower()        
          string = list(s)
          i = 0         
          j = ( len(s) - 1 )       
     
          while i < j:             
                string[i] ,string[j] = string[j],string[i]             
                i += 1 
                j -= 1     
    
          return (s == ''.join(string)) 
    

    Though this is not as short as the other solution examples, I find this fairly simple to understand and fairly fast as well (65ms). Also works with string containing a newline character :-)


  • 0
    S

    @siegfried Your solution won't work if there are > 1 consecutive non isalnum() characters.

    To overcome it you'll need to put a while instead of if/elif.

    To ensure that multiple increments/decrements does not result in violation of condition l < r, @caikehe had placed the condition check of l < r in the inner while loops as well.


  • 0

    @sdliuyuzhi Maybe you don't need continue.


  • 1
      def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s: return True
        l, r = 0, len(s)-1
        while l < r:
          sl = s[l].lower()
          sr = s[r].lower()
          if s[l].isalnum() and s[r].isalnum():
            if sl != sr:
              return False
            l += 1
            r -= 1
          else:
            if not s[l].isalnum():
              l += 1
            if not s[r].isalnum():
              r -= 1
        return True
    

Log in to reply
 

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