代码语言：javascript复制
今天分享leetcode第19篇文章，也是leetcode第20题—有效的括号（Valid Parentheses），地址是：https://leetcode.com/problems/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 :Input: "()"
Output: true
【中文题目】给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例:输入: "()"
输出: true
【思路】我们可以使用栈保留左括号，每遇到一个右括号，从栈中弹出一个左括号，并判断是否和右括号对应。【代码】python版本class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
ls = []
# 使用字典，节省代码，否则要分别判断括号对应关系
d = {'}':'{', ')':'(', ']':'['}
for si in s:
if si in '([{':
ls.append(si)
else:
# ls没有元素或者元素不匹配
if len(ls) == 0 or d[si] != ls[-1]:
return False
else:
ls.pop()
return len(ls) == 0
C 版本class Solution {
public:
bool isValid(string s) {
stack<char> ls;
map<char, char> d;
// 使用字典，节省代码，否则要分别判断括号对应关系
d['}'] = '{';
d[')'] = '(';
d[']'] = '[';
for(char si:s){
if(si == '{' or si == '(' or si == '[')
ls.push(si);
else{
// ls没有元素或者元素不匹配
if((ls.size() == 0) or (d[si] != ls.top()))
return false;
// 弹出元素
ls.pop();
}
}
return ls.size() == 0;
}
};
