#20 Valid Parentheses

題目描述

給你一個字串s只由字元'(',')','[',']','{','}'所組成，判斷這個字串是符合規則的。

合格的字串必須：

開放的括弧必須使用相對應的同型括弧來閉合。
括弧必須要以正確的順序來閉合。
每個閉合的括弧都是由兩個同型別的開放括弧組成。

限制條件

1 <= 字串s長度 <= 10^4
字串s只會由"()[]{}"組成。
開放括弧指的是單個括弧'(',')','[',']','{','}'。
閉合括弧指的是"()","[]","{}"。
閉合要按照一定的順序指的是"{[()]}"，順序錯誤指的是"{([})]"。

解題思路

Stack

這是一個配對消除遊戲，括弧全部配對成功就過關，因此每配對出一個括弧，我們就可以把它消除，當遇到無法消除的情況時，就回傳失敗。

無法消除的情況有 "找不到對應的括弧"、 "順序錯誤"、 "字串全部檢查完後還有剩餘的括弧沒有消除" 這三種。

找不到對應的括弧很好理解，就是烙單的括弧'(',')','[',']','{','}'等，沒有形成"()","[]","{}"，所以無法消除。

而消除必須按照順序，指的是如果有一個'('找到了')'，可以組成"()"，這樣就算成功消除，但如果中間夾了一個其他的括弧像是"([)"、"(])"、"({)"等等的形式，按照順序的話必須先消除中間夾著的括弧才能繼續下去，這幾個範例無法消除，所以要回傳失敗。

檢查過一遍字串後還有剩餘的括弧舉例來說像是"([()]"、"()("、"())"，按照順序是可以把大部分的括弧配對完，但是最後會依序剩下"("、"("、")"這幾個烙單的括弧無法消除，所以是不符合規則的結果。

測試例子：

"("，失敗，沒有對應的括弧可以消除。
")"，失敗，沒有對應的括弧可以消除。
"()"，成功，可以全部消除。
"())"，失敗，沒有全部消除。
"([{}])"，成功，可以按照順序由內而外全部消除。
"([{]})"，失敗，雖然數量一樣，但是沒有辦法按照順序全部消除。

所以在通過所有失敗判定後，剩下的就是成功的結果。

解決的策略是，如果遇到右括弧'(','[','{'先保存起來，等遇到左括弧')',']','}'時，和保存的右括弧中最後一個放進去的括弧配對，配對成功就可以把這個右括弧刪掉，繼續檢查下一個字元，直到檢查完整個字串。

在資料結構上有很多選擇，Array、List、Stack或者是Deque都可以，而最適合拿來解決這一題的是具有先進後出FILO特性的Stack。

public class Solution {
    public bool IsValid(string s) {
		//排除不符合條件的數值
		if(s.Length<0 || s.Length>10000) return false;
		//
        var st = new Stack();
        foreach(char i in s){
            if(i=='('||i=='['||i=='{'){
                st.Push(i);

			//處理 )、]、}
            }else{ 
				//沒有可以配對的結果
                if(st.Count==0) return false;
				//
                if((char)st.Peek()=='(' && i==')') st.Pop();
                else if((char)st.Peek()=='[' && i==']') st.Pop();
                else if((char)st.Peek()=='{' && i=='}') st.Pop();
                //順序錯誤
                else return false;
            }
        }
		//還有剩餘就是False。
        return st.Count==0;
    }
}

複雜度分析：

時間複雜度：由於每次都需要檢查完整個字串，需要花費單位時間s.Length，因此時間複雜度為O(n)。
空間複雜度：stack在最差的情況下會儲存s.length/2個字元，因此複雜度為O(n)。

學習重點

學習Stack的應用方式，先進後出(FILO)的特性。