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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个字符串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

      以上是 在Python中检查表达式O(1)空间O（N ^ 2）时间复杂度的圆括号 的全部内容， 来源链接： utcz.com/z/321890.html

      回到顶部