iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
0

題目


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 的倒數,所以我就開始陷入到底怎麼效能調校的世界裡.../images/emoticon/emoticon02.gif

這題很明顯就是要大家練習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 是用 linqs.ElementAt(i) ,後來才改成 s[i] 或是轉成 ToCharArray ,效能就快將近三倍 (176ms -> 64ms)。

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

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


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


上一篇
[Day 3] 演算法刷題 LeetCode 1. Two Sum (Easy)
下一篇
[Day 5] 演算法刷題 LeetCode 70. Climbing Stairs (Easy)
系列文
透過 LeetCode 解救美少女工程師的演算法人生31

1 則留言

0
rockywang
iT邦新手 5 級 ‧ 2019-10-20 09:38:53

初學者我 submit 了好幾次,想要測試看看效能的差異 >"<

發現有兩點特別是重點,一是不要用 Map (應該是相對於 C# 的 Dictionary)
用了以後我只能排在 Java 版的第三名,改用 char[] 後就變第一名了

不要用 Map 是關鍵我想大概是因為在放三個括號的對應時,Map 還需要做一些計算才知道要放在記憶體的哪裡

再來的關鍵,不要宣告成 Character[],因為這樣放進去或取出來比對時應該都要做一次自動轉型
若只是宣告成 Character[] 不再使用 Map,就會是第二名,程式需要花 1ms
再改成 char[] 後就第一名了,程式花 0ms

你可以試試 :)

    public boolean isValid(String s) {
    	
    	int length = s.length();
    	if (length % 2 != 0)
    		return false;
  
    	int top = -1;
    	char brackets[] = new char[length];
    	
    	for (char aChar : s.toCharArray()) {
    		if (aChar == '{' || aChar == '(' || aChar == '[') {
    			brackets[++top] = aChar;
    		}
    		// 不是開始字元,pop 取出取得對應字元比對是否正確
    		else {
    			if (top == -1)
    				return false;
    			char popChar = brackets[top--];
    			if (aChar == '}' && popChar != '{')
    				return false;
    			else if (aChar == ')' && popChar != '(')
    				return false;
    			else if (aChar == ']' && popChar != '[')
    				return false;
    		}
    	}
    	
    	return top == -1;
    }

我要留言

立即登入留言