演算法養成記：有效括弧

• 2020 年 3 月 10 日
• 筆記

LeetCode20

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.

中文意思就是：

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。

有效字元串需滿足：

1.左括弧必須用相同類型的右括弧閉合。

2.左括弧必須以正確的順序閉合。

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

在實際測試里，

執行耗時是：2ms，1ms

記憶體消耗是:37.4MB,37.3MB

這題不難，但是嘗試了好多種寫法，一直都是2ms，接近崩潰。直到想到判斷其他括弧的時候，如果匹配上了就可以跳出循環了，用了圖二的continue，出現1ms，擊敗98.92%的用戶，懸著的心才下來，但是測試效果也不太穩定，希望各位小夥伴也提供下思路。

有個收穫就是，之前寫棧的時候，判斷空，直接就用了stack.empty()；測試中，使用這個方法一直都比stack.size()>0好記憶體高，看了下empty()的方法，裡面還是去拿了size()來判斷，還套了兩層，這的確是沒有必要了。

數據結構和演算法一直都是程式設計師面試重點。寫好每一個方法，每一個介面，程式的效率也會越來越高。為了學習和鞏固數據結構和演算法，我們特別創作了《呆萌程式設計師–明明凱凱演算法養成記》，每天更新一篇數據結構知識點或者刷一道LeetCode題目。演算法都會在LeetCode上測試。當然答案不唯一，由於能力有限，實現方法不一定是最好的，也希望各位小夥伴一起來學習分享~