題目: 20. Valid Parentheses
難度: Easy
===========================================================================
說明:
給予s字串裡面會(huì)包含下面6種字元:
'(', ')', '{', '}', '[', ']'
每個(gè)左括號(hào)必須匹配相同類型的右括號(hào)
===========================================================================
測(cè)資1:
Input: s = "([)]"
Output: false
測(cè)資2:
Input: s = "{[]}"Output: true
===========================================================================
條件限制:
1<=s字串長(zhǎng)度<=10^4
s字串只由6個(gè)字元組成:'(', ')', '[', ']', '{', '}'
===========================================================================
解題:
使用stack先進(jìn)後出的特性,
當(dāng)碰到左括弧,將其放入stack,
遇到右括弧,使用Pop()取出最新的一筆值,驗(yàn)證是否為對(duì)應(yīng)的左括弧
使用Pop()若stack為空,會(huì)產(chǎn)生error,表示當(dāng)前左括弧的數(shù)量較右括弧少,
當(dāng)字串搜索完成,若stack已被清空,表示該字串是正確的.
public class Solution
{
public bool IsValid(string s)
{
Stack<char> sta = new Stack<char>();
try //若一開始就為右括弧則會(huì)產(chǎn)生錯(cuò)誤
{
foreach (char c in s)
{
if (c == '(' || c == '[' || c == '{') //若為左括弧則放到stack
sta.Push(c);
else if (c == ')' && sta.Pop() != '(') //若為右括弧則判斷是否有對(duì)應(yīng)的左括弧
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:"["
}
}
達(dá)人
