C++实现LeetCode(20.验证括号)-662P.COM

这篇文章主要介绍了C++实现LeetCode(20.验证括号),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

[LeetCode] 20. Valid Parentheses 验证括号

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

这道题让我们验证输入的字符串是否为括号字符串，包括大括号，中括号和小括号。这里需要用一个栈，开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，若此时栈为空，则直接返回 false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回 false，代码如下：

方法一：

class Solution {

public:

bool isValid(string s) {

stack<char> parentheses;

for (int i = 0; i < s.size(); ++i) {

if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]);

else {

if (parentheses.empty()) return false;

if (s[i] == ')' && parentheses.top() != '(') return false;

if (s[i] == ']' && parentheses.top() != '[') return false;

if (s[i] == '}' && parentheses.top() != '{') return false;

parentheses.pop();

}

return parentheses.empty();

}

};

方法二：

class Solution {

public:

bool isValid(string s) {

int n = s.size();

if (n % 2 == 1) {

return false;

}

unordered_map<char, char> pairs = {

{')', '('},

{']', '['},

{'}', '{'}

};

stack<char> stk;

for (char ch: s) {

if (pairs.count(ch)) {

if (stk.empty() || stk.top() != pairs[ch]) {

return false;

}

stk.pop();

}

else {

stk.push(ch);

}

return stk.empty();

}

};

c++

[LeetCode] 20. Valid Parentheses 验证括号

0评论