索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github:
https://github.com/illuz/leetcode
020.Valid_Parentheses (Easy)
链接：
题目：https://oj.leetcode.com/problems/valid-parentheses/
代码(github)：https://github.com/illuz/leetcode
题意：
判断1个括号字符串是不是是有效的。
分析：
直接用栈摹拟，很简单的。
Java 的括号匹配可以用 if 写，也能够用 HashMap<Character, Character> 存，还可以用 "(){}[]".indexOf(s.substring(i, i + 1)。 （这个讨论也能够用于 C++ 和 Python）
这里的 C++ 是用 if 匹配， Java 用 indexOf， Python 用 dict。
代码：
C++:
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
int len = s.length();
for (int i = 0; i < len; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
stk.push(s[i]);
} else {
if (stk.empty())
return false;
if (stk.top() == '(' && s[i] == ')')
stk.pop();
else if (stk.top() == '[' && s[i] == ']')
stk.pop();
else if (stk.top() == '{' && s[i] == '}')
stk.pop();
else
return false;
}
}
return stk.empty();
}
};
Java:
public class Solution {
public boolean isValid(String s) {
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i < s.length(); ++i) {
int pos = "(){}[]".indexOf(s.substring(i, i + 1));
if (pos % 2 == 1) {
if (stk.isEmpty() || stk.pop() != pos - 1)
return false;
} else {
stk.push(pos);
}
}
return stk.isEmpty();
}
}
Python:
class Solution:
# @return a boolean
def isValid(self, s):
mp = {')': '(', ']': '[', '}': '{'}
stk = []
for ch in s:
if ch in '([{':
stk.append(ch)
else:
if not stk or mp[ch] != stk.pop():
return False
return not stk