[LeetCode] 020. Valid Parentheses (Easy) (C++/Java/Python)
來源：程序員人生 發布時間：2015-03-16 10:30:01 閱讀次數：2583次
索引：[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
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
