Python, breadth first search with set() data structure, time O(n^2) and space O(n)


  • 0
    A

    For this problem, we update all status space with each chars in string s. Each status is the count of unpaired '(', at each update we only keep 0 and positive counts and remove replicated count with set() data structure. We return true only if we have at least one 0 count in the final status space.

    For example, "((**)":
    initial: current_step = ([0])
    "(": current_step = ([1])
    "((": current_step = ([2])
    "((*": current_step = ([1, 2, 3])
    "((**": current_step = ([0, 1, 2, 3, 4])
    "((**)": current_step = ([0, 1, 2, 3])

    Time and space complexity analysis:
    The worst case is a string contains 100 "*"(since we only scale the status space when we meet "*"), you may find that we only keep non-negative unique status(remove all replicates), the minimum count is 0 and maximum count is 100. So the space complexity is O(n)

    Since we search all status space for each chars in string s, time complexity is O(n^2)

    class Solution(object):
        def checkValidString(self, s):
            """
            :type s: str
            :rtype: bool
            """
            if not s:
                return True
    
            current_step, next_step = set([0]), set()
            for ch in s:
                while current_step:
                    num = current_step.pop()
                    if ch == '(':
                        next_step.add(num + 1)
                    elif ch == ')':
                        if num - 1 >= 0:
                            next_step.add(num - 1)
                    else:
                        next_step.add(num)
                        next_step.add(num + 1)
                        if num - 1 >= 0:
                            next_step.add(num - 1)
                            
                current_step, next_step = next_step, current_step
    
            if current_step and 0 in current_step:
                return True
    
            return False
    

Log in to reply
 

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