Leetcode-20 Valid Parentheses

发表于 | 分类于 | 次

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1

1
2
Input: "()"
Output: true

Example 2

1
2
Input: "{[]}"
Output: true

Example 3

1
2
Input: "([)]"
Output: false

解题思路

很自然想到用栈。从前往后遍历字符串，若当前为左括号，入栈；若当前为右括号且无法消除，返回 false。无法消除的情况包括：1、栈为空；2、栈顶左括号与该右括号不匹配。最后，若栈不为空，说明还有多余的左括号，返回 false。

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$，最坏情况下，栈中包含所有字符，如：((((((((((((。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	bool isValid(string s) {
		stack<char> cs;
		unordered_map<char, char> mp = { {')','('},{']','['},{'}','{'} };
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
				cs.push(s[i]);
			}
			else {
				if (cs.empty()) return false;
				if (mp[s[i]] != cs.top()) return false;
				cs.pop();
			}
		}
		return cs.empty();
	}
};