1. 题目
https://leetcode-cn.com/problems/valid-parentheses/
https://leetcode.com/problems/valid-parentheses/
判断一个字符串里面的括号是否从左到右成对出现。
{[()]} - true((()))[[[]]] - true{[} - false{()}] - false(( - false([)] - false
2. 思路
- 遍历每个字符，用 stack 来存放左括号；
- 遇到右括号的时候，对比 stack 最近添加的符号，假如正好配成一对，就把这个左括号移出 stack，否则直接返回 false；
- 遍历结束之后 stack 应该为空；
- 特殊情况：
- 字符串的数量是奇数（不可能配成有效对）；
- stack 为空时，看到了一个右括号；
选择的数据结构
- Stack - 后进先出
- Dictionary - 根据右括号找左括号
踩过的坑
- 尝试了把每个符号转换成一个数字，最终验证求和是否为 0 （这个解法不满足配对顺序的要求，只能满足左右符号数量相等）
- 用 Regex 来匹配字符的效率很低
- 用 switch case 来找到配对的左括号不如用 Dictionary 来的快
- 需要先把 string 变成 char array，这样比直接用 string 来得快
结果
70-80ms 左右。
3. 我的解法（C#）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public class Solution {
private Dictionary<char, char> mappings = new Dictionary<char, char>
{
{'}', '{'},
{']', '['},
{')', '('}
};
public bool IsValid(string s)
{
Stack<char> charStack = new Stack<char>();
char[] arr = s.ToCharArray(); // faster than using string
// odd number
if (arr.Count() % 2 == 1)
return false;
for (int i = 0; i < arr.Count(); i++)
{
char c = arr[i];
if (charStack.Count() == 0 && mappings.ContainsKey(c))
return false;
else
{
if(mappings.ContainsKey(c))
if (charStack.Peek() == mappings[c])
charStack.Pop();
else
return false;
else
charStack.Push(c);
}
}
return charStack.Count() > 0 ? false : true;
}
}
|
4. 优化
- 把 for loop 里面的 if-else 逻辑改写成了另一种形式，但是最终的速度差不多；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
// 1. change if-else logic
public class Solution
{
private Dictionary<char, char> mappings = new Dictionary<char, char>
{
{'}', '{'},
{']', '['},
{')', '('}
};
public bool IsValid(string s)
{
Stack<char> charStack = new Stack<char>();
char[] arr = s.ToCharArray(); // faster than using string
// odd number
if (arr.Count() % 2 == 1)
return false;
for (int i = 0; i < arr.Count(); i++)
{
char c = arr[i];
// check 2 scenarios
if ((charStack.Count() == 0 && mappings.ContainsKey(c)) || (mappings.ContainsKey(c) && charStack.Peek() != mappings[c]))
return false;
else if (mappings.ContainsKey(c) && charStack.Peek() == mappings[c])
charStack.Pop();
else
charStack.Push(c);
}
return charStack.Count() > 0 ? false : true;
}
}
|
- 把 for loop 改成 foreach，最终速度也差不多；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
// 2. use for loop instead of foreach loop
public class Solution
{
private Dictionary<char, char> mappings = new Dictionary<char, char>
{
{'}', '{'},
{']', '['},
{')', '('}
};
public bool IsValid(string s)
{
Stack<char> charStack = new Stack<char>();
char[] arr = s.ToCharArray(); // faster than using string
// odd number
if (arr.Count() % 2 == 1)
return false;
foreach (char c in arr)
{
// check 2 scenarios
if ((charStack.Count() == 0 && mappings.ContainsKey(c)) || (mappings.ContainsKey(c) && charStack.Peek() != mappings[c]))
return false;
else if (mappings.ContainsKey(c) && charStack.Peek() == mappings[c])
charStack.Pop();
else
charStack.Push(c);
}
return charStack.Count() > 0 ? false : true;
}
}
|
- 另外还看到有人说为了避免 Peek 报错，可以在创建 stack 的时候给一个初始值，我试了之后发现速度也差不多。
结语
欢迎大家分享更好的解法~
