@@ -0,0 +1,2068 @@
+from collections import Counter%0Aclass Solution(object):%0A    def dfs(self, s, pos, stack):%0A        if stack + self.min_possible_opening%5B-1%5D - self.min_possible_opening%5Bpos%5D %3E self.max_possible_closing%5B-1%5D - self.max_possible_closing%5Bpos%5D:%0A            return False%0A        if stack + self.max_possible_opening%5B-1%5D - self.max_possible_opening%5Bpos%5D %3C self.min_possible_closing%5B-1%5D - self.min_possible_closing%5Bpos%5D:%0A            return False%0A        if pos == len(s):%0A            return not stack%0A        if s%5Bpos%5D == '(':%0A            stack += 1%0A            if self.dfs(s, pos + 1, stack):%0A                return True%0A            stack -= 1%0A        elif s%5Bpos%5D == ')':%0A            if not stack:%0A                return False%0A            else:%0A                stack -= 1%0A                if self.dfs(s, pos + 1, stack):%0A                    return True%0A                stack += 1%0A        else:%0A            if stack: # treat as ')'%0A                stack -= 1%0A                if self.dfs(s, pos + 1, stack):%0A                    return True%0A                stack += 1%0A            # treat as '('%0A            stack += 1%0A            if self.dfs(s, pos + 1, stack):%0A                return True%0A            stack -= 1%0A%0A            # treat as ''%0A            if self.dfs(s, pos + 1, stack):%0A                return True%0A        return False%0A%0A    def checkValidString(self, s):%0A        %22%22%22%0A        :type s: str%0A        :rtype: bool%0A        %22%22%22%0A        c = Counter(s)%0A        mpo, mpc = c%5B'('%5D + c%5B'*'%5D, c%5B')'%5D + c%5B'*'%5D%0A%0A        self.max_possible_opening = %5B0%5D%0A        self.min_possible_opening = %5B0%5D%0A        self.max_possible_closing = %5B0%5D%0A        self.min_possible_closing = %5B0%5D%0A        for c in s:%0A            self.min_possible_opening.append(self.min_possible_opening%5B-1%5D + (c == '('))%0A            self.max_possible_opening.append(self.max_possible_opening%5B-1%5D + (c != ')'))%0A            self.min_possible_closing.append(self.min_possible_closing%5B-1%5D + (c == ')'))%0A            self.max_possible_closing.append(self.max_possible_closing%5B-1%5D + (c != '('))%0A%0A        return self.dfs(s, 0, 0)%0A

Add py solution for 678. Valid Parenthesis String