Coding

LeetCode 20. Valid Parentheses

By Anthea / 芫荽 12月 21, 2022 5 min read

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:

Input: s = "()" 
Output: true

Example 2:

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

Example 3:

Input: s = "(]" 
Output: false

直覺

要完整閉合代表字串長度必須是偶數，所以先把不是偶數的過濾掉。

var length = s.Length; 
 
var isOdd = length % 2 == 0; 
if (!isOdd) return false;

secondParentheses：比對目標
used：已經比對完成且有成對的符號索引

var secondParentheses = new Dictionary<string, string>() 
{ 
    {")", "("}, 
    {"]", "["}, 
    {"}", "{"}, 
}; 
 
var used = new Dictionary<int, int>();

以下面這個例子來說，我在 index = 3 ) 的時候應該要配對到 index = 0 ( ，index = 4 ] 的時候，雖然可以配對到 index = 1 [，但因為 [] 的符號區間踩到了 () 的區間範圍，所以會回傳 false。

( [ { ) ] } 
0 1 2 3 4 5 
 
|/////|-|-|  ---> () 
0 1 2 3 4 5 
 
|-|/////|-|  ---> [] 
0 1 2 3 4 5

這裡我把它整理成兩個邏輯：

從結尾的符號找開頭的符號
開頭和結尾的符號索引區間，必須完整包含或被包含在任何一組其他索引區間內

有找到結尾符號（ secondParentheses 的 Keys ），就再從原本的字串找出所有和他相符的開頭符號（secondParentheses 的 Values），並利用 Except 去除已經在 used 內，被比對過的索引。如果這裡的數量等於 0 ，代表所有的開頭符號都被比對過了，不是封閉的符號區間，回傳 false 。

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 內的數量，是否和字串內應有的書量一致：

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;

完整的程式碼如下：

var length = s.Length; 
 
var isOdd = length % 2 == 0; 
if (!isOdd) return false; 
 
var secondParentheses = new Dictionary<string, string>() 
{ 
    {")", "("}, 
    {"]", "["}, 
    {"}", "{"}, 
}; 
 
var used = new Dictionary<int, int>(); 
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 內最後一個符號和現在拿到的是否相同。

( [ { ) ] } 
0 1 2 3 4 5 
 
0 ( --> 放入 ) 
1 [ --> 放入 ] 
2 { --> 放入 } 
3 ) --> 拿一個出來，是 }，不符合，false

( [ { } ] ) 
0 1 2 3 4 5 
 
0 ( --> 放入 ) 
1 [ --> 放入 ] 
2 { --> 放入 } 
3 } --> 拿一個出來，是 } 
4 ] --> 拿一個出來，是 ] 
5 ) --> 拿一個出來，是 )

if (s.Length % 2 != 0) return false; 
 
var openParentheses = new Dictionary<char, char>() 
{ 
    {'(', ')'}, 
    {'[', ']'}, 
    {'{', '}'}, 
}; 
 
var shouldUsedClosedParentheses = new Stack<char>(); 
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)