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

題目敘述

題目會給定一個字串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