Fork me on GitHub

leetcode之20. 有效的括号

发表于 | 分类于
字数统计 529 字 | 阅读时长 2 分钟

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

1
2
3
> 输入: "()"
> 输出: true
>

示例 2:

1
2
3
> 输入: "()[]{}"
> 输出: true
>

示例 3:

1
2
3
> 输入: "(]"
> 输出: false
>

示例 4:

1
2
3
> 输入: "([)]"
> 输出: false
>

示例 5:

1
2
3
> 输入: "{[]}"
> 输出: true
>

解题思路：

思路一：

​ 时间复杂度：$O(n)$,空间复杂度：$O(n)$.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
public:
	bool isValid(string s) {
		stack<char> sta;
		int flag = 1;
		for(int i = 0; i < s.length(); i++)
		{
			char a = s[i];
			int is_ok = 0;
			switch(a)
			{
				case '{':
				case '(':
				case '[':
					sta.push(a);
					break;
				case '}':
				{
					if(sta.empty()) {flag = 0;}
					else
					{
						if(sta.top() == '{')
						{
							sta.pop();
							flag = 1;
						}
						else
						{
							flag = 0;
							is_ok = 1;
						}
					}
					break;
				}
				case ')':
				{
					if(sta.empty()) {flag = 0;}
					else
					{
						if(sta.top() == '(')
						{
							sta.pop();
							flag = 1;
						}
						else
						{
							flag = 0;
							is_ok = 1;
						}
					}
					break;
				}
				case ']':
				{
					if(sta.empty()) {flag = 0;}
					else
					{
						if(sta.top() == '[')
						{
							sta.pop();
							flag = 1;
						}
						else
						{
							flag = 0;
							is_ok = 1;
						}
					}
					break;
				} 
			}
			if (is_ok) break;
		} 
		if(!sta.empty()) return 0;
		else return flag;
	}
};

思路二：

使用stack存储字符，时间复杂度：$O(n)$，空间复杂度：$O(n)$.

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
37
38
39
class Solution{
    public:
    	bool isValid(string s)
        {
            stack<char> st;
            for(int j = 0; j < s.length() ;j ++)
            {
            	// 首先判断是否是[{(，入栈
                if(s[j] == '['|| s[j] == '{' || s[j] == '(')
                {
                    st.push(s[j]);
                }
            	// 如果栈是空的，说明里面都是空白字符
                else if(st.empty()){
                    return false;
                }
            	// 接下来判断是否能配对
                else 
                {
                    if(s[j] == ']' && st.top() != '[')
                    {
                        return false;
                    }
                    else if(s[j] == '}' && st.top() != '{')
                    {
                        return false;
                    }
                    else if(s[j] == ')' && st.top() != '(')
                    {
                        return false;
                    }
            		// 如果上面的那些情况都不成立，也就是说，配对成功，此时出栈
                    st.pop();
                }
            }
            // 最后返回这个栈是否为空，如果为空，则匹配成功，否则失败
            return st.empty();
        }
};