String Parenthesis

Algorithms
dfs, string
Catalogue
  1. 1. 678. Valid Parenthesis String
  2. 2. 22. Generate Parentheses

678. Valid Parenthesis String

  • If you use stack to solve this question, it will be complex to handle different cases!
  • If you use dfs to search if is valid, it will be time consuming!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def checkValidString(self, s):
        low = high = 0
        for ch in s:
            if ch == '(':
                low += 1
                high += 1
            elif ch == ')':
                low = max(0, low-1)
                high -= 1
                if high < 0:
                    return False
            else: # "*"
                low = max(0, low-1)
                high += 1
        return low == 0

22. Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def generateParenthesis(self, n):
        res = []
        self.dfs(0, 0, n, [], res)
        return res

    def dfs(self, left, right, n, path, res):
        if right == n:
            res.append(''.join(path))
            return

        if left < n:
            self.dfs(left + 1, right, n, path + ['('], res)

        if right < left:
            self.dfs(left, right + 1, n, path + [')'], res)
  • Follow up : 3 {}, 2(), 1[]
Share