#20.Valid Parentheses
Problem statement
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"
Output: true
Example 3
Input: s = "(]"
Output: false
Explanation
給定一個字串其內容僅有 (
、)
、[
、]
、{
、}
六種括號來組成,其括號的使用方式和規則與數學運算使用時的相同,例如 (
僅能以 )
關閉,請確認字串是否為有效
Solution
一開始先將奇數長度的字串排除,因為括號為倆倆一組,不會有單一括號存在。
建立一個堆疊來裝載後續迴圈內判斷出的右括號,使用一迴圈迭代字串內所有字符,在每次迭代中,判斷當前字符是否為任一左括號,如果是,則在堆疊中存入對應的右括號;如果當前符號為右括號,將堆疊最上方的元素推出,比較兩者是否一樣,若一樣繼續下次迴圈,否則直接返回 false
在最後一個 else if
中除了上述的判斷之外,如果迴圈尚未結束,但堆疊內已經沒有任何元素,表示已經沒有對應的括號,直接返回 false
迴圈結束後,如果堆疊內還有元素存在,也表示沒有相對應的括號,故最後直接返回堆疊內數量是否等於零的判斷結果
public bool IsValid(string s)
{
if (s.Length % 2 != 0) return false;
Stack<char> stack = new Stack<char>();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
stack.Push(')');
else if (s[i] == '[')
stack.Push(']');
else if (s[i] == '{')
stack.Push('}');
else if (stack.Count == 0 || s[i] != stack.Pop())
return false;
}
return stack.Count == 0;
}
Reference
Thanks for reading the article 🌷 🌻 🌼
If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐
or buy me a coffee ⬇️ I'd appreciate it.
Top comments (0)