題目: 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:"["
}
}