O(n) intuitive python solution


  • 0
    Z
    def validPalindrome2(s):
            """
            :type s: str
            :rtype: bool
            """
            if len(s)==1 or len(s)==2:
                return True
            start = 0
            end = len(s)-1
            while start < end:
                if s[start]==s[end]:
                    start+=1
                    end-=1
                else:
                    break
            if start>=end:
                return True
            else:
                newStart = start + 1
                newEnd = end
                while newStart < newEnd:
                    if (s[newStart]==s[newEnd]):
                        newStart+=1
                        newEnd-=1
                    else:
                        break
                if newStart>=newEnd:
                    return True
                else:
                    newStart = start
                    newEnd= end - 1
                    while newStart < newEnd:
                        if (s[newStart]==s[newEnd]):
                            newStart+=1
                            newEnd-=1
                        else:
                            break
                    if newStart >= newEnd:
                        return True
                    else:
                        return False

Log in to reply
 

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