[LeetCode] 020. Valid Parentheses (Easy) (C++/Java/Python)

索引：[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

题意：

判断一个括号字符串是否是有效的。

分析：

直接用栈模拟，很简单的。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();elsereturn 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 booleandef 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 Falsereturn not stk

每天告诉自己一次，『我真的很不错』