iT邦幫忙

0

LeetCode 20221207 #2 (20. Valid Parentheses; Easy)

JT 2022-12-07 20:15:12933 瀏覽
  • 分享至 

  • xImage
  •  

題目連結: 20. Valid Parentheses; Easy

題目說明:

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.
Every close bracket has a corresponding open bracket of the same type.

簡單來說就是判斷字串中左括弧與右括弧是否都成對顯示。

Example1

Input: s = "()"
Output: true

Example2

Input: s = "()[]{}"
Output: true

Example3

Input: s = "(]"
Output: false

Example4

Input: s = "{[]}"
Output: true

Example5

Input: s = "()}}"
Output: false

本次解題心得:

利用Stack後進先出的特性,剛好可以使用在左右成對的比較()、{}、[],直接排除有問題的配對,不符合題目條件的有哪些呢?

  1. 字串是空值or null
  2. 字元數不能被2整除
  3. 出現左括弧時,若沒有相對應的右括弧

自己的解答:

public class Solution {
    public bool IsValid(string s) {
            if (string.IsNullOrWhiteSpace(s))
                return false;

            if ((s.ToCharArray().Length % 2) != 0) //不是成對的char
                return false;

            Stack<char> st = new Stack<char>(); //使用Stack來存放,特性:先進後出

            foreach (char ch in s)
            {
                if (ch == '(' || ch == '{' || ch == '[')
                    st.Push(ch);

                if (st.Count() == 0) //剛開始與最後,如果出現連續兩個右括弧,Stack.Pop()會出現exception
                    return false;

                if ( ch == ')' && st.Pop() != '(' )
                    return false;

                if (ch == '}' && st.Pop() != '{')
                    return false;

                if (ch == ']' && st.Pop() != '[')
                    return false;
            }

            return st.Count() == 0; //如果Stack還有未配對的括弧,代表false
    }
}

參考別人優化後的解答:

public class Solution {
    public bool IsValid(string s) {
            Stack<char> st = new Stack<char>();

            foreach (var ch in s)
            {
                if (ch == '(') 
                { 
                    st.Push(')'); //右括弧(出現時,把相對應的左括弧)存進Stack
                    continue; //離開迴圈,繼續執行下一字元
                }

                if (ch == '{')
                {
                    st.Push('}'); //右括弧{出現時,把相對應的左括弧}存進Stack
                    continue;
                }

                if (ch == '[')
                {
                    st.Push(']'); //右括弧[出現時,把相對應的左括弧]存進Stack
                    continue;
                }

                if (st.Count == 0 || ch != st.Pop()) //左括弧出現,若沒有相對應的右括弧Pop出來,則表示不成對
                    return false;
            }

            return st.Count() == 0; //如果Stack還有未配對的括弧,表示不成對
    }
}

參考資料來源:
[LeetCode C#] 20. Valid Parentheses — Stack
C# Solution - elegant and simple 7 lines (Runtime: faster than 99.90%; Memory: less than 48.94%)


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言