題目

https://leetcode.com/problems/valid-parentheses/

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

解答

C#

public class Solution 
{
    public bool IsValid(string s) 
    {
        Dictionary<char, char> dic = new Dictionary<char, char>();
        dic.Add('}', '{');
        dic.Add(']', '[');
        dic.Add(')', '(');

        if (s.Length % 2 == 1)
            return false;

        var stack = new Stack<char>();

        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];

            if (dic.ContainsValue(c))
            {
                stack.Push(c);
            }
            else
            {
                if (stack.Count == 0)
                    return false;
                if (stack.Peek() == dic[c])
                    stack.Pop();
            }

        }
        return stack.Count == 0;   
    }
}

結果

Runtime: 64 ms, faster than 99.94% of C# online submissions.

Memory Usage: 21.2 MB, less than 6.38% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

這次寫的難度其實並不高，但是效能一開始是沒有被 LeetCode 接受。

後來接受但是是執行時間是 176ms，且排行所有 submissions 的倒數，所以我就開始陷入到底怎麼效能調校的世界裡...

這題很明顯就是要大家練習Stack、先進後出的概念，不論有多少個、有多少種的左括號，都要與右括號成對，並且後進的括號就要先配對。

1. 使用 Dictionary 去記錄成對的括號
2. 先判斷若 string 長度不是 2 的倍數就回傳 false，因為括號一定會是成對的
3. for 迴圈逐一判斷字串裡的字元
   • 若 s[i] 字元是 左括號，並存在在 Dictionary，則將此左括號 Push 到 Stack 裡
   • 若 s[i] 字元是 右括號
     • 且 stack.Count == 0，代表Stack裡面沒有剩餘的左括號可以配對，所以回傳 false。
     • 且 stack 的第一個字元 (stack.peek) 是剛好配對的右括號，則將 stack 裡的左括號拿出來，代表配對成功。
4. 迴圈結束後，再檢查 stack 是否還有其它字元
   • 若有，就代表有剩餘的括號沒有配對成功，則回傳 false
   • 若無，則代表所有括號都配對成功，則回傳 true。

示意圖

如果看文字敘述不是很明確的話，可以看下面的示意圖。

效能調校

其實我寫了大概五六種的寫法，但是效能都大同小異，我也參考了別人的寫法，跟我的差別是不大的。後來我想了一下，會不會是我用了 linq 的關係？

我本來拿 string 裡的 char 是用 linq 的 s.ElementAt(i) ，後來才改成 s[i] 或是轉成 ToCharArray ，效能就快將近三倍 (176ms -> 64ms)。

我後來在網路上查看有沒有類似的 case ，但幾乎是沒有，只有黑暗執行緒大大有講過 linq 可能有效能上的問題。

若是其他人有 linq 上效能的想法，可以寄信或留言跟我聊聊，因為小妹我也滿好奇的。

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉