Python BFS + Check + Memorizing


  • 1
    1. Remove char by char(except those alphabets) and put the newly formed string into a queue, if it's the first time to reach to a valid string, stop inviting new strings and keep pop the queue until it's empty.

    2. In order to make the program faster, try to keep track of what's already judged, and store into a set.

    class Solution(object):
        def removeInvalidParentheses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            dic, st = {}, set()
            def judge(s):
                if s in dic:
                    return dic[s]
                dic[s] = False
                cnt = 0
                for c in s:
                    if c != '(' and c != ')':
                        continue
                    elif c == '(':
                        cnt += 1
                    elif cnt != 0:
                        cnt -= 1
                    else:
                        return False
                return cnt == 0
    
            queue = collections.deque()
            queue.append(s)
            f = 0
            ans = []
            while queue:
                front = queue.popleft()
                if judge(front):
                    ans.append(front)
                    f = 1
                if not f:
                    for i in xrange(len(front)):
                        if front[i] != '(' and front[i] != ')':
                            continue
                        if front[:i] + front[i + 1:] not in st:
                            queue.append(front[:i] + front[i + 1:])
                            st.add(front[:i] + front[i + 1:])
            return ans
    

  • 0
    J

    You need to update the dic just before you return from judge, otherwise you are only caching the negative results.


Log in to reply
 

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