O(n) time O(1) concise Python solution


  • 0
    C

    TLE for recursion.
    Inspired by https://discuss.leetcode.com/topic/103946/o-n-java-solution
    We always wants the two condition to be True, so scan the string
    I write it in python with some modifications

    class Solution(object):
        def checkValidString(self, s):
            """
            :type s: str
            :rtype: bool
            """
            leftcnt, rightcnt = 0, 0
            for i in range(len(s)):
                if s[i] == ')':
                    leftcnt -= 1
                else:
                    leftcnt += 1
                if leftcnt < 0:
                    return False
                if s[len(s)-i-1] == '(':
                    rightcnt -= 1
                else:
                    rightcnt += 1
                if rightcnt < 0:
                    return False
            return True

Log in to reply
 

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