【leetcode】20. Valid Parentheses（Python & C++）

---

20. Valid Parentheses

题目链接

20.1 题目描述：

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.

20.2 解题思路：

思路一：利用栈。遍历字符串，每次遇到左括号时，就入栈，遇到右括号时，判断栈为空或者栈顶字符与此时的右括号不匹配，则返回FALSE，否则，出栈。遍历结束，如果栈为空，则返回true，否则为false。

思路二：分c++和Python。

c++：同思路一一样，不同的是写法上做了调整，没有使用if，而是用了switch。Python：利用字典，原理一样，不过写法上更简洁。

20.3 C++代码：

1、思路一代码（3ms）：

class Solution107_0 { public: bool isValid(string s) { if (s.length() < 2 || s.length() % 2 == 1 || s[0] == ')' || s[0] == ']' || s[0] == '}') return false; stack<char>v; for (int i = 0; i < s.length(); i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { v.push(s[i]); } if (s[i] == ')' || s[i] == ']' || s[i] == '}') { char temp = v.top(); v.pop(); if ((s[i] == ')' && temp == '(') || (s[i] == ']' && temp == '[') || (s[i] == '}' && temp == '{')) continue; else return false; } } return v.empty(); } };

2、思路二代码（3ms）：

class Solution107_1 { public: bool isValid(string s) { if (s.length() < 2 || s.length() % 2 == 1 || s[0] == ')' || s[0] == ']' || s[0] == '}') return false; stack<char>v; for (int i = 0; i < s.length();i++) { switch (s[i]) { case '(': case '[': case '{': v.push(s[i]); break; case ')': if (v.empty() || v.top() != '(') return false; else v.pop(); break; case ']': if (v.empty() || v.top() != '[') return false; else v.pop(); break; case '}': if (v.empty() || v.top() != '{') return false; else v.pop(); break; } } return v.empty(); } };

20.4 Python代码：

1、思路一代码（39ms）：

class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ v=[] a=['(','{','['] for i in range(len(s)): if s[i] in a: v.append(s[i]) continue elif s[i]==')': if len(v)==0 or v.pop()!='(': return False elif s[i]==']': if len(v)==0 or v.pop()!='[': return False elif s[i]=='}': if len(v)==0 or v.pop()!='{': return False return len(v)==0

2、思路二代码（49ms）

class Solution1(object): def isValid(self, s): """ :type s: str :rtype: bool """ v=[] d={']':'[',')':'(','}':'{'} for i in range(len(s)): if s[i] in d.values(): v.append(s[i]) elif s[i] in d.keys(): if len(v)==0 or d[s[i]]!=v.pop(): return False return len(v)==0

---