有效的括号（Leetcode）

2020-12-29

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#）

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. 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，最终速度也差不多；

// 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 的时候给一个初始值，我试了之后发现速度也差不多。

结语

欢迎大家分享更好的解法~