DAY 4
0
Software Development

## 題目

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>();

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)`

## 為什麼我要這樣做？

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。

## 效能調校

### 1 則留言

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

``````    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;
}
}