DEV Community

Cover image for Valid Parentheses
FakeStandard
FakeStandard

Posted on • Edited on

2 1

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
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: s = "()[]{}"
Output: true
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: s = "(]"
Output: false
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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.


Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️