题目
有一个里面有左括号跟右括号的字串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