九章演算法 | Google 面試題：有效括弧字元串

撰文 | JZ

專欄 | 九章演算法

題目描述

給定一個字元串，由（ * ）三個字元組成，判斷是否滿足要求左括弧和有括弧一一對應，且對應的左括弧必定在右括弧前面。其中，*可以被當做一個單獨的左括弧，右括弧或者可以當做不存在

樣例

1. Input: "()" Output: True2. Input: "(*)" Output: True //*被當做空字元，不存在3. Input: "(*))" Output: True //星號被當做左括弧

解題思路分析

首先進行最基礎的考慮，（在不考慮星號的情況下）我們必定會選擇位置最接近的左右括弧配對，這樣避免了人為造成的右括弧前面沒有左括弧匹配的慘劇。因此我們在寫程序進行處理的時候，對於每個右括弧判斷前面是否有1個左括弧能被他擁有，如果左括弧數量不足，這個字元串必定是false，或者當整個串被匹配完之後發現有多餘的左括弧，這個字元串同樣是false

接下來考慮有星號的情況:」)」必須由位置在它之前的」(」或」*」匹配，如果」(」或者」*」數量不足導致的false是無法避免的，而如果」(「 比」）」多，將」(」與」*」優先匹配可以減小false的可能性。舉個例子如樣例3，從左往右遍歷的時候，優先匹配」（」和」*」，遇見第一個」)」，發現沒有單獨的」(」,從」(*」的組合中拆出一個」(「與之匹配，而原先匹配中的*因為可以等同於不存在便不予理會，接著遇到第二個」)」,拿走剛才剩餘的」*」。綜上我們可以觀察到，」(」容易受制於」)」而將其與」*」匹配後就很靈活，不僅避免了數量太多帶來的麻煩，也能在和*匹配後再次提供自身給」)」進行匹配。而如果這樣匹配結束還有多餘的」(」則必定false

我們設l（left）為必須被右括弧匹配的左括弧數量，cp（couple）為前面左括弧和星號數量。遍歷字元串，遇到左括弧和星號的時候,cp++; 遇到右括弧的時候cp—; 遇到星號，默認先於前面的左括弧(l>0)匹配,此時(l—)，遇到右括弧，默認先與前面必須與右括弧匹配的左括弧匹配，此時(l—;cp—;)或者在支援兵中考慮(cp—) 注意cp是前方左右的左括弧和星號數量，一旦cp<0即false. 匹配完發現(l>0)即多出了左括弧，也為false。剩下的情況就是true了

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

一道簡單的思維題，考慮到星號在其中的用處就能解決

lintcode相關問題

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧