資料結構
網路
關係型資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python中檢查表示式中括號是否平衡（空間複雜度O(1)，時間複雜度O(N^2)）
假設我們有一個包含這些括號'('，')'，'{'，'}'，'['和']'的字串str，我們需要檢查括號是否平衡。當開括號和閉括號型別相同且括號按正確順序閉合時，我們可以說括號是平衡的。
因此，如果輸入類似於{([])}, 則輸出為True。
為了解決這個問題，我們將遵循以下步驟：
- cnt := 0
- i := 0
- j := -1
- 定義一個函式solve()。這將接收s, temp作為引數
- cnt := cnt - 1
- s := 將s轉換為新的列表
- 如果 j > -1 且 s[j] 與 temp 相同，則
- s[i] := '#'
- s[j] := '#'
- 當 j >= 0 且 s[j] 等於 '#' 時，迴圈執行：
- j := j - 1
- i := i + 1
- 返回 1
- 否則：
- 返回 0
- 在主方法中，執行以下操作：
- 如果 s 的大小為 0，則
- 返回 True
- 否則：
- ans := False
- 當 i < s 的大小且不為零時，迴圈執行：
- 如果 s[i] 等於 '}'，則
- ans := solve(s, '{')
- 如果 ans 等於 0，則
- 返回 False
- 否則，如果 s[i] 等於 ')'，則
- ans := solve(s, '(')
- 如果 ans 等於 0，則
- 返回 False
- 否則，如果 s[i] 等於 ']'，則
- ans := solve(s, '[')
- 如果 ans 等於 0，則
- 返回 False
- 否則：
- j := i
- i := i + 1
- cnt := cnt + 1
- 如果 s[i] 等於 '}'，則
- 如果 cnt 不等於 0，則
- 返回 False
- 返回 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
更新於: 2020-08-27
361 次瀏覽
廣告