2023-11-01|閱讀時間 ‧ 約 5 分鐘

一魚多吃 用stack來驗證 合法括弧字串 678. Valid Parenthesis String

raw-image

題目敘述

題目會給定一個字串s,裡面都是由()*打散交錯而成。

配對規則

左括弧 ( 可以和 右括弧 ) 配對,其中 左括弧一定要在右括弧的左邊。

左括弧 ( 也可以和 *星號 配對,其中 左括弧一定要在*星號的左邊。

問我們給定的輸入字串s是否為合法括弧配對字串?

例如 s = "()(*" ,是合法括弧配對字串。

又例如s = "()*(" ,不是合法括弧配對字串。

詳細的題目敘述在這裡:


測試範例

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

約束條件

Constraints:

  • 1 <= s.length <= 100
  • s[i] is '('')' or '*'.

演算法

這題也可以用到前面學過的stack配對模型的模板來實作。

先建立兩個堆疊,第一個叫做stk,第二個叫做star

stk 用來記錄 左括弧( 的陣列索引位置

star用來記錄 *星號 的陣列索引位置

每次遇到左括號,就推入當下的索引

每次遇到右括號,則依序下列規則進行

  1. 假如stk非空,代表還有 左括弧( 可以配對,pop頂端元素。
  2. 假如star非空,代表還有 *星號 可以配對,pop頂端元素。
  3. 假如都沒有,代表當下的 右括號) 無法配對,直接return False,代表輸入為非法字串


接著,假如stk和star還有殘留,則依序檢查是否每個左括弧(都在對應*星號的左邊。
假如不是,代表殘留的左括弧(*星號無法配對,直接return False,代表輸入為非法字串


最後,全部配對完之後,檢查stk是否為空,代表全部配對完成。



程式碼

class Solution:
 def checkValidString(self, s: str) -> bool:
  
  # store the indices of '('
  stk = []
  
  # store the indices of '*'
  star = []
  
  
  for idx, char in enumerate(s):
   
   if char == '(':
    stk.append( idx )
    
   elif char == ')':
    
    if stk:
     stk.pop()
    elif star:
     star.pop()
    else:
     return False
   
   else:
    star.append( idx )
  
  
  # cancel ( and * with valid positions, i.e., '(' must be on the left hand side of '*'
  while stk and star:
   if stk[-1] > star[-1]:
    return False
  
   stk.pop()
   star.pop()
  
  
  # Accept when stack is empty, which means all braces are paired
  # Reject, otherwise.
  return len(stk) == 0
    

複雜度分析

時間複雜度: O( n )
從頭到尾,每個字元檢查過一遍。

空間複雜度: O( n )
需要兩個stack,stack耗用空間最多和字串長度一樣長。


關鍵知識點

在於理解並且活用stack 先進後出FILO的特質,來實作括號配對

記得回去複習 合法括號配對這題,主要的原理是相通的。


Reference:

[1] Python O(n) by stack. 85%+ [w/ Comment] - Valid Parenthesis String - LeetCode

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.