> ## Content Index > Fetch the complete content index at: https://blog.anthea.day/llms.txt > Use this file to discover other available public pages before exploring further. # LeetCode 20. Valid Parentheses - URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-2/ - Published: 2022-12-21T01:44:47.000Z - Updated: 2026-11-07T18:26:10.000Z - Author: Anthea / 芫荽 - Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記 > 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. **Example 1:** ```vbnet Input: s = "()" Output: true ``` **Example 2:** ```vbnet Input: s = "()[]{}" Output: true ``` **Example 3:** ```vbnet Input: s = "(]" Output: false ``` --- ### 直覺 要完整閉合代表字串長度必須是偶數，所以先把不是偶數的過濾掉。 ```kotlin var length = s.Length; var isOdd = length % 2 == 0; if (!isOdd) return false; ``` - `secondParentheses`：比對目標 - `used`：已經比對完成且有成對的符號索引 ```csharp var secondParentheses = new Dictionary() { {")", "("}, {"]", "["}, {"}", "{"}, }; var used = new Dictionary(); ``` 以下面這個例子來說， 我在 `index = 3` `)` 的時候應該要配對到 `index = 0` `(` ，`index = 4` `]` 的時候，雖然可以配對到 `index = 1` `[`，但因為 `[]` 的符號區間踩到了 `()` 的區間範圍，所以會回傳 `false`。 ```perl ( [ { ) ] } 0 1 2 3 4 5 |/////|-|-| ---> () 0 1 2 3 4 5 |-|/////|-| ---> [] 0 1 2 3 4 5 ``` 這裡我把它整理成兩個邏輯： 1. 從結尾的符號找開頭的符號 2. 開頭和結尾的符號索引區間，必須完整包含或被包含在任何一組其他索引區間內 有找到結尾符號（ `secondParentheses` 的 `Keys` ），就再從原本的字串找出所有和他相符的開頭符號 （`secondParentheses` 的 `Values`），並利用 `Except` 去除已經在 `used` 內，被比對過的索引。如果這裡的數量等於 `0` ，代表所有的開頭符號都被比對過了，不是封閉的符號區間，回傳 `false` 。 ```javascript var list = s.Select(c => c.ToString()).ToList(); for (var index = 1; index < length; index++) { var currentString = s.Substring(index, 1); var isSecondParenthesis = secondParentheses.TryGetValue(currentString, out var firstParenthesis); if (isSecondParenthesis) { var indexes = Enumerable.Range(0, list.Count) .Where(i => list[i] == firstParenthesis && i < index) .ToList(); var except = indexes.Except(used.Keys).ToList(); if (except.Count == 0) return false; } } ``` 如果有的話，開頭必須是離結尾符號最近的前一個，最近也就是索引最大 。所以現在我們有結尾符號 `index` ，和開頭符號 `previousIndex` ，接著要確認 `index` 到 `previousIndex` 的區間，是否有出現沒有完整包含的符號區間。 也就是 `previousIndex` < `otherPreviousIndex` < `index` < `otherIndex` ，有的話就 `false`，沒有的話就代表比對成功，可以把這組索引存入 `used`。最後都沒有中途比對失敗的話，要確認 `used` 內的數量，是否和字串內應有的書量一致： ```kotlin var list = s.Select(c => c.ToString()).ToList(); for (var index = 1; index < length; index++) { var currentString = s.Substring(index, 1); var isSecondParenthesis = secondParentheses.TryGetValue(currentString, out var firstParenthesis); if (isSecondParenthesis) { var indexes = Enumerable.Range(0, list.Count) .Where(i => list[i] == firstParenthesis && i < index) .ToList(); var except = indexes.Except(used.Keys).ToList(); if (except.Count == 0) return false; var previousIndex = except.Max(); var isOverload = used.Any(x => x.Key < previousIndex && previousIndex < x.Value && x.Value < index); if (isOverload) return false; used[previousIndex] = index; } } return used.Count == length / 2; ``` 完整的程式碼如下： ```java var length = s.Length; var isOdd = length % 2 == 0; if (!isOdd) return false; var secondParentheses = new Dictionary() { {")", "("}, {"]", "["}, {"}", "{"}, }; var used = new Dictionary(); var list = s.Select(c => c.ToString()).ToList(); for (var index = 1; index < length; index++) { var currentString = s.Substring(index, 1); var isSecondParenthesis = secondParentheses.TryGetValue(currentString, out var firstParenthesis); if (isSecondParenthesis) { var indexes = Enumerable.Range(0, list.Count) .Where(i => list[i] == firstParenthesis && i < index) .ToList(); var except = indexes.Except(used.Keys).ToList(); if (except.Count == 0) return false; var previousIndex = except.Max(); var isOverload = used.Any(x => x.Key < previousIndex && previousIndex < x.Value && x.Value < index); if (isOverload) return false; used[previousIndex] = index; } } return used.Count == length / 2; ``` 結果：Runtime 2503 ms / Memory 42.8 MB （高到嚇人 😵‍💫，爬了一下底層，Except 有跑 foreach、Max 有跑 while、Any 有跑 foreach，再加上原本的 for，應該是因為這樣 😵） --- ### 最佳解：使用 Stack `Stack` 的特性是**後進先出**，很適合用在這個例子上：如果是開頭符號就塞一個結尾符號到 `Stack` 裡，如果是結尾符號就去比對 `Stack` 內最後一個符號和現在拿到的是否相同。 ```rust ( [ { ) ] } 0 1 2 3 4 5 0 ( --> 放入 ) 1 [ --> 放入 ] 2 { --> 放入 } 3 ) --> 拿一個出來，是 }，不符合，false ``` ```rust ( [ { } ] ) 0 1 2 3 4 5 0 ( --> 放入 ) 1 [ --> 放入 ] 2 { --> 放入 } 3 } --> 拿一個出來，是 } 4 ] --> 拿一個出來，是 ] 5 ) --> 拿一個出來，是 ) ``` ```csharp if (s.Length % 2 != 0) return false; var openParentheses = new Dictionary() { {'(', ')'}, {'[', ']'}, {'{', '}'}, }; var shouldUsedClosedParentheses = new Stack(); foreach (var c in s) { // 如果是開頭符號 if (openParentheses.ContainsKey(c)) { // 把結尾符號加入應該被使用的 Stack 中 shouldUsedClosedParentheses.Push(openParentheses[c]); } // 如果是結尾符號 else if (openParentheses.ContainsValue(c)) { // 應該被使用的結尾符號數量不應該是 0 // Stack 中最後一個應該要是現在的結尾符號 c if (usedClosedParentheses.Count == 0 || usedClosedParentheses.Pop() != c) return false; } else { return false; } } // 應該被使用的結尾符號比對完之後，應該要被清除 return shouldUsedClosedParentheses.Count == 0; ``` 結果：Runtime 117 ms（55.3%） / Memory 36.8 MB（50.51%） --- #### 參考資料 - [C# faster than 99.4% — (with comments)](https://leetcode.com/problems/valid-parentheses/solutions/256800/c-faster-than-99-4-with-comments/?ref=blog.anthea.day)