Luna Tech

Tutorials For Dummies.

有效的括号(Leetcode)

2020-12-29


1. 题目

https://leetcode-cn.com/problems/valid-parentheses/

https://leetcode.com/problems/valid-parentheses/

判断一个字符串里面的括号是否从左到右成对出现。


2. 思路

  1. 遍历每个字符,用 stack 来存放左括号;
  2. 遇到右括号的时候,对比 stack 最近添加的符号,假如正好配成一对,就把这个左括号移出 stack,否则直接返回 false;
  3. 遍历结束之后 stack 应该为空;
  4. 特殊情况:
    • 字符串的数量是奇数(不可能配成有效对);
    • stack 为空时,看到了一个右括号;

选择的数据结构

踩过的坑

结果

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. 优化

  1. 把 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;
	}
}
  1. 把 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;
	}
}
  1. 另外还看到有人说为了避免 Peek 报错,可以在创建 stack 的时候给一个初始值,我试了之后发现速度也差不多。

结语

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