Re: [閒聊] 每日leetcode已回收
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 678. Valid Parenthesis String
: 給你一個只包含 "(",")","*" 的字串s，"*" 可以是左括號、右括號或空字串，求出s是
: 否可以組成一個合法的括號表達式。
思路：
差不多
用兩個stack分別記錄左括號和*的位置
遇到右括號優先找有沒有左括號，沒有再去找有沒有*
如果都沒有就回傳false
遍歷完s後會有兩種可能
1.還有多的左括號
2.沒有多的左括號
沒有左括號的話就可以直接回傳true了
還有多的左括號，就要去看有沒有*的位置在左括號的右邊
就這樣一直判斷到左括號的stack清空為止
golang code:
func checkValidString(s string) bool {
stack:=[]int{}
rec:=[]int{}
for key,val:=range s{
if val=='('{
stack=append(stack,key)
}else if val==')'{
if len(stack)>0{
stack=stack[:len(stack)-1]
}else if len(rec)>0{
rec=rec[:len(rec)-1]
}else{
return false
}
}else{
rec=append(rec,key)
}
}
if len(stack)>len(rec){
return false
}
for len(stack)>0{
if stack[len(stack)-1]>rec[len(rec)-1]{
return false
}else{
stack=stack[:len(stack)-1]
rec=rec[:len(rec)-1]
}
}
return true
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.26.211 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712472749.A.851.html
→
04/07 14:57,
1年前
, 1F
04/07 14:57, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 99 之 1548 篇)：