題目
有一個裡面有左括號跟右括號的字串s
跟一個只含0跟1的陣列locked
如果locked的第i項是1的話
s[i]可以選擇要是左括號還是右括號
locked[i]是0的話s[i]就固定
最後要回傳s有沒有符合3個條件其中一個
s=() s=(A) s=(A B...)其中AB也是valid parenthese string
思路
如果len(s)是奇數 括號不可能會平衡
接著從左邊向右檢查
看有沒有足夠的左括號讓固定的右括號平衡
檢查完再從右邊往左邊掃
看有沒有足夠的右括號讓固定的左括號平衡
都沒問題的就回傳True
Python Code:
class Solution(object):
def canBeValid(self, s, locked):
if len(s)%2==1:
return False
left,right=0,0
for i in range(len(s)):
if locked[i]=='1' and s[i]==')':
right+=1
if right>i+1-right:
return False
for i in range(len(s)-1,-1,-1):
if locked[i]=='1' and s[i]=='(':
left+=1
if left>len(s)-i-left:
return False
return True
每次取變數都不知道要取什麼：0