主題

[LeetCode C#] 20. Valid Parentheses - Stack

帥氣跳蚤蛋 | 2021-07-11 21:16:48 | 巴幣 0 | 人氣 61

題目: 20. Valid Parentheses
難度: Easy
===========================================================================
說明:
給予s字串裡面會包含下面6種字元:
'(', ')', '{', '}', '[', ']'
每個左括號必須匹配相同類型的右括號
===========================================================================
測資1:
Input: s = "([)]"
Output: false

測資2:
Input: s = "{[]}"Output: true
===========================================================================
條件限制:
1<=s字串長度<=10^4
s字串只由6個字元組成:'(', ')', '[', ']', '{', '}'
===========================================================================
解題:
使用stack先進後出的特性,
當碰到左括弧,將其放入stack,
遇到右括弧,使用Pop()取出最新的一筆值,驗證是否為對應的左括弧
使用Pop()若stack為空,會產生error,表示當前左括弧的數量較右括弧少,
當字串搜索完成,若stack已被清空,表示該字串是正確的.

public class Solution
{
    public bool IsValid(string s)
    {
        Stack<char> sta = new Stack<char>();
        try //若一開始就為右括弧則會產生錯誤
        {
            foreach (char c in s)
            {
                if (c == '(' || c == '[' || c == '{')   //若為左括弧則放到stack
                    sta.Push(c);
                else if (c == ')' && sta.Pop() != '(')  //若為右括弧則判斷是否有對應的左括弧
                    return false;
                else if (c == ']' && sta.Pop() != '[')
                    return false;
                else if (c == '}' && sta.Pop() != '{')
                    return false;
            }
        }
        catch
        {
            return false;
        }

        return sta.Count == 0;  //若stack中還有括弧表示有括弧沒匹配到ex:"["
    }
}

創作回應

相關創作

更多創作