Valid Parentheses

#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:

1. Open brackets must be closed by the same type of brackets.
2. 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

LeetCode Solution

GitHub Repository

---

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 ⭐ I'd appreciate it.

---