Leetcode: Valid Parentheses
Leetcode: Valid Parentheses
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 16:02:37
发布于 2019-01-22 16:02:37
题目： Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
分析： 遍历字符串，使用栈依次存储字符，遇到’0’，’]’，’}’出栈进行判断。 注意：’(‘和’)’只差为1，’[‘和’]’只差为2，’{‘和’}’只差为2，这可以帮助我们判读左括号和右括号是否成对。 C++示例代码：
class Solution
{
public:
bool isValid(string s)
{
string::size_type length = s.length();
//如果给定的字符个数为奇数，直接返回false
if (length % 2)
{
return false;
}
stack<char> chstack;
char top;//当前栈顶的元素
//用于记录current和previous元素只差，'('和')'只差为1，'['和']'只差为2，'{'和'}'只差为2
int distance;
for (size_t i = 0; i < length; i++)
{
if (s[i] == ')' || s[i] == ']' || s[i] == '}')
{
if (chstack.empty())
{
return false;
}
else
{
top = chstack.top();
chstack.pop();
distance = s[i] - top;
//判断previous和current是否匹配
if (distance != 1 && distance != 2)
{
return false;
}
}
}
else
{
chstack.push(s[i]);
}
}
//栈为空返回true，否则肯定有不匹配的括号在栈中返回false
return chstack.empty() ? true : false;
}
};C#示例代码：
public class Solution
{
public bool IsValid(string s)
{
if (s.Length % 2 == 1) return false;
Stack<char> chstack = new Stack<char>();
char top= ' ';
int distance = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == ')' || s[i] == ']' || s[i] == '}')
{
if (chstack.Count == 0)
{
return false;
}
else
{
top= chstack.Pop();
distance = s[i] - top;
if (distance != 1 && distance != 2)
{
return false;
}
}
}
else
{
chstack.Push(s[i]);
}
}
return chstack.Count == 0 ? true : false;
}
}Python代码： Python代码我没有使用判读左括号和右括号距离的方法
class Solution:
# @return a boolean
def isValid(self, s):
length = len(s)
stack = []
if length % 2 != 0:
return False
for i in range(length):
if s[i] == ')' or s[i] == ']' or s[i] == '}':
if not stack:
return False
else:
top = stack.pop()
if top == '(' and s[i] != ')' or top == '[' and s[i] != ']' or top == '}' and s[i] != '}':
return False
else:
stack.append(s[i])
if stack:
return False
else:
return True本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月20日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读