0%

[Leetcode]20. Valid Parentheses(C++)

题目描述

题目链接:20. Valid Parentheses

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

An input string is valid if:

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

例子

例子 1

Input: s = "()"
Output: true

例子 2

Input: s = "()[]{}"
Output: true

例子 3

Input: s = "(]"
Output: false

例子 4

Input: s = "([)]"
Output: false

例子 5

Input: s = "{[]}"
Output: true

Follow Up

Note

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

解题思路

这道题可以用栈来解。首先建立一个哈希表记录左右括号之间的对应的关系。然后从头遍历字符串,遇到左括号压入栈中,遇到右括号时有三种情况:

  • 栈为空,表示当前左边没有左括号,或者所有左括号都匹配了,所以返回 false
  • 栈顶为对应的左括号,此时可以用于匹配当前右括号。将其弹出,继续遍历
  • 栈顶为不对应的左括号,表示最近的没匹配的左括号不能匹配,类似于 [) 返回 false

除此之外在最开始可以做个长度判断,如果是奇数可以直接返回 false,代码如下:

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
#include <string>
#include <stack>
#include <unordered_map>

class Solution {
public:
bool isValid(std::string s) {

if (s.length() % 2 == 1) return false;

std::stack<char> stk;
std::unordered_map<char, char> pairs ({
{'(', ')'},
{'[', ']'},
{'{', '}'}
});

for (int i = 0; i < s.length(); i++) {
if (pairs.count(s[i])) {
stk.push(s[i]);
} else {
if (stk.empty() || s[i] != pairs[stk.top()]) return false;
stk.pop();
}
}

return stk.empty();
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 20.ValidParentheses.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions