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

更新於 發佈於 閱讀時間約 4 分鐘
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

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
題目敘述 題目會給定我們一個字串s,和一組字庫wordDict。 問我們能不能透過字串串接的方式,從字庫裡面的字拼成原本的字串s? 可以的話,返回True。 無解的話,返回False。 註: 題目還允許重複使用字庫裡面的字去串接。
Thumbnail
題目敘述 題目會給定我們一個字串s,和一組字庫wordDict。 問我們能不能透過字串串接的方式,從字庫裡面的字拼成原本的字串s? 可以的話,返回True。 無解的話,返回False。 註: 題目還允許重複使用字庫裡面的字去串接。
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
Thumbnail
題目會給定一個字串s,裡面都是由()*打散交錯而成。 配對規則 左括弧 ( 可以和 右括弧 ) 配對,其中 左括弧一定要在右括弧的左邊。 左括弧 ( 也可以和 *星號 配對,其中 左括弧一定要在*星號的左邊。 問我們給定的輸入字串s是否為合法括弧配對字串?
Thumbnail
題目會給定一個字串s,裡面都是由()*打散交錯而成。 配對規則 左括弧 ( 可以和 右括弧 ) 配對,其中 左括弧一定要在右括弧的左邊。 左括弧 ( 也可以和 *星號 配對,其中 左括弧一定要在*星號的左邊。 問我們給定的輸入字串s是否為合法括弧配對字串?
Thumbnail
題目會給定兩個字串s,t,把裡面的井字號#視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部依照規則處理完以後,s,t剩下的字串內容兩者是否相等?
Thumbnail
題目會給定兩個字串s,t,把裡面的井字號#視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部依照規則處理完以後,s,t剩下的字串內容兩者是否相等?
Thumbnail
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s裡面,最長的合法括弧配對字串長度是多少? 例如 s = "()()" ,最長的合法括弧配對字串長度為4
Thumbnail
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s裡面,最長的合法括弧配對字串長度是多少? 例如 s = "()()" ,最長的合法括弧配對字串長度為4
Thumbnail
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s 是不是合法括弧自串,也就是所有的右括弧都在左括弧後面,而且可以兩兩相消。
Thumbnail
題目會給定一個字串s,裡面都是由() [] {}打散交錯而成。 問我們給定的輸入字串s 是不是合法括弧自串,也就是所有的右括弧都在左括弧後面,而且可以兩兩相消。
Thumbnail
Valid Parentheses : 確認input的括號是否符合成雙成對的規則,符合回傳true,否則回傳false.
Thumbnail
Valid Parentheses : 確認input的括號是否符合成雙成對的規則,符合回傳true,否則回傳false.
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News