在Python中检查表达式O(1)空间O（N ^ 2）时间复杂度的圆括号

假设我们有一个字符串str，其中包含这些括号'（'，'）'，'{'，'}'，'['和']'，我们必须检查括号是否平衡。可以说，当开括号和闭括号类型相同时，括号是平衡的。支架以正确的顺序关闭。

因此，如果输入类似于{（[]]}，则输出将为True。

为了解决这个问题，我们将遵循以下步骤-

• cnt：= 0

• i：= 0

• j：= -1

• 定义一个功能solve()。这需要s，临时

• cnt：= cnt-1

• s：=来自s的新列表

• 如果j> -1并且s [j]与temp相同，则

• j：= j-1

• s [i]：='#'

• s [j]：='#'

• 当j> = 0且s [j]与'#'相同时，执行

• 我：=我+ 1>

• 返回1

• 除此以外，

• 返回0

• 从主要方法中，执行以下操作-

• 如果s的大小等于0，则

• 返回True

• 除此以外，

• 返回False

• 如果s [i]与'}'相同，则

• j：=我

• 我：=我+ 1

• cnt：= cnt + 1

• ans：= solve（s，'['）

• 如果ans与0相同，则

• 返回False

• ans：= solve（s，'（'）

• 如果ans与0相同，则

• 返回False

• 返回False

• ans：= solve（s，'{'）

• 如果ans与0相同，则

• 否则，当s [i]与'）'相同时，则

• 否则，当s [i]与']'相同时，则

• 除此以外，

• 回答：= False

• 当我<的大小不为零时，

• 如果cnt不等于0，则

• 返回True

示例

让我们看下面的实现以更好地理解-

cnt = 0
i = 0
j = -1
def solve(s, temp):
   global i, j, cnt
   cnt -= 1
   s = list(s)
   if j > -1 and s[j] == temp:
      s[i] = '#'
      s[j] = '#'
      while j >= 0 and s[j] == '#':
         j -= 1
      i += 1
      return 1
   else:
      return 0
def bracketOrderCheck(s):
   global i, j, cnt
   if len(s) == 0:
      return True
   else:
      ans = False
      while i < len(s):
         if s[i] == '}':
            ans = solve(s, '{')
            if ans == 0:
               return False
         elif s[i] == ')':
            ans = solve(s, '(')
            if ans == 0:
               return False
         elif s[i] == ']':
            ans = solve(s, '[')
            if ans == 0:
               return False
         else:
            j = i
            i += 1
            cnt += 1
      if cnt != 0:
         return False
      return True
print(bracketOrderCheck("{([])}"))

输入值

"{(()[])}"

输出结果

True