2018-10-11二分之N平方是因为 replace 带来的时间复杂码？作者回复: 对的，replace本身的操作是 o(n) 的，所以最坏情况下会有产生 n^2 的复杂度。
13
2019-01-14刷题的时候发现老师讲的使用map的实例答案并不对，elif判断应该判断stack为空或map对应，按照老师的思路用java实现了一下
public boolean isValid(String s)
{
//---------------Use Map----------------------
char[] chars=s.toCharArray();
Stack<Character> stack=new Stack<Character>();
Map<Character,Character> map= new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
for(char c:chars){
if(!map.containsKey(c)){
stack.push(c);
}
else if(stack.isEmpty() || map.get(c)!=stack.pop()){
return false;
}
}
return stack.isEmpty();
}展开 2 10
2018-11-11用python解题虽然写起来简单，但是如果面试笔试的时候不让用高级语言岂不是一脸懵逼了。。 5
2019-01-03C solution：Runtime: 0 ms, faster than 100.00% of C online submissions for Valid Parentheses.
bool isValid(char* s) {
int len = strlen(s);
char *temp = malloc(sizeof(char)*(len+1)/2);
int p = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
temp[p] = s[i];
p++;
} else {
if (p == 0) {
return false;
} else {
if ((s[i] == ')' && temp[p-1] != '(') || (s[i] == ']' && temp[p-1] != '[') || (s[i] == '}' && temp[p-1] != '{')) {
return false;
} else {
temp[p-1] = '\0';
p--;
}
}
}
}
return strlen(temp) == 0;
}展开作者回复: 赞👍🏻👍🏻
2
2018-12-11GO语言实现：
type Stack []string
func (s *Stack) Pop() string {
ns := *s
v := ns[len(ns)-1]
*s = ns[:len(ns)-1]
return v
}
func isValid(s string) bool {
var stack Stack
hash_map := map[string]string{
")":"(",
"]":"[",
"}":"{",
}
for _, b := range s {
if _, ok := hash_map[string(b)]; !ok {
stack = append(stack, string(b))
} else if len(stack) == 0 || stack.Pop() != hash_map[string(b)] {
return false
}
}
return len(stack) == 0
}展开作者回复: 👍🏻👍🏻👍🏻
2- 2018-11-26如果用对称数组思想会不会更好呢：如果为奇数直接false，为偶数则从中间向两边遍历对比 。这样时间复杂度最大也只是n/2
作者回复: ()(())
2 
2018-10-12想不到啊，如果没看过，根本想不到作者回复: 对的，这个题目的解法，不管算法本身上，还是写出来的程序代码，都比较给人启示。
2
2019-07-17根据老师思路 JavaScript实现：
function isValid(str) {
const stack = []
const bracketsMap = { ')': '(', ']': '[', '}': '{' }
for (let i = 0; i < str.length; i++) {
const s = str[i]
// 如果是左括号压入栈
if (!(s in bracketsMap)) {
stack.push(s)
} else if (!stack.length || bracketsMap[s] !== stack.pop()) {
return false
}
}
return !stack.length
}
console.log(isValid('{}')) // true
console.log(isValid('(){}')) // true
console.log(isValid('({)}')) // false
console.log(isValid('((({}))')) // false
console.log(isValid('))')) // false展开 1
2019-03-28swift 版本
class Solution {
func isValid(_ s: String) -> Bool {
var stack:[String] = []
var initialParentheses:[String: String] = [")":"(","]":"[","}":"{"]
for c in s {
if !initialParentheses.keys .contains(String(c)) {
stack.append(String(c));
} else if stack.count > 0 && initialParentheses[String(c)] != stack.removeLast() {
return false
}
}
if stack.count == 0 {
return true;
} else {
return false
}
}
}展开作者回复: 帅！ 最后一句可以简化：
return stack.count == 0; 1
2019-02-16
java : class Solution {
// 自己实现版本1
/*public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0 ; i < s.length() ; i ++){
char temp = s.charAt(i);
if(temp == '(' || temp == '{' || temp == '['){
stack.push(temp);
continue;
}else if(temp == ')' && (stack.isEmpty() || stack.pop() != '(')){
return false;
}else if(temp == '}' && (stack.isEmpty() || stack.pop() != '{')){
return false;
} else if(temp == ']' && (stack.isEmpty() || stack.pop() != '[')){
return false;
}
}
if(!stack.isEmpty()){
return false;
}
return true;
}*/
// 按老师讲的实现版本2
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put('}','{');
map.put(']','[');
for(char c : s.toCharArray()){
if(!map.containsKey(c)){
stack.push(c);
}else if( stack.isEmpty() || map.get(c) != stack.pop()){
return false;
}
}
if(!stack.isEmpty()){
return false;
}
return true;
}
}展开作者回复: 帅！
1
2018-10-12第二种方法的空间复杂度是不是O(n^2)?作者回复: 对的，就是 O(n^2)
1
2018-10-11有点神奇啊 1
2020-02-07leetcode上实际的test case要比课程中介绍的情况多很多，所以我发现直接按照视频里的代码，并不能完全access，还有某些变态的边界条件没考虑到。
2020-01-26按照老师的思想用GO实现了一遍
func isValid(s string) bool {
str := strings.Split(s, "")
strLen := len(str)
var sMap = make(map[string]string, 3)
sMap["{"] = "}"
sMap["["] = "]"
sMap["("] = ")"
stack := make([]string, 0)
var tail string
for i := 0; i < strLen; i++ {
// 栈顶无元素时，新插入元素为}、]、)之一则不合法
stackLen := len(stack)
if stackLen < 1 {
tail = ""
} else {
tail = stack[:][stackLen-1]
}
if tail == "" {
if str[i] == "}" || str[i] == "]" || str[i] == ")" {
return false
}
}
// 栈顶元素与新插入元素为一对时，如{与}、[与]、(与)，则对对碰消除，否则将新元素直接入栈
// fmt.Printf("tail: %v, stack: %v, cur ele: %v\n", tail, stack, str[i])
if sMap[tail] == str[i] {
stack = stack[0 : len(stack)-1]
} else {
stack = append(stack, str[i])
}
// fmt.Printf("cur stack: %v: stack len: %d\n", stack, len(stack))
}
// 全部入栈后，栈为空则合法，不为空则不合法
return len(stack) == 0
}展开
2019-12-31第一个not stack的地方应该为stack吧？- 2019-10-22JavaScript搬
var isValid = function(s) {
var map = {
")": "(",
"]": "[",
"}": "{"
} // 写一个字典，建立对应关系
var stack = []
for(let key of s){
if(!map.hasOwnProperty(key)){
stack.push(key)
}else{
if(stack.pop() != map[key]){
return false
}
}
}
return !stack.length;
};展开作者回复: Cool!
2019-10-21是否需要判断栈中长度，如果大于一半就可以直接return false了呢？作者回复: 可以的。是一个不错的优化。
- 2019-10-07使用JS来实现该算法：
var isValid = function(s) {
var stack = [];
// key 是右括号
var paren_map = { ")": "(", "]": "[", "}": "{" };
for (var c of s) {
// 只把左括号放进stack
if (!paren_map[c]) {
stack.push(c);
continue;
}
// 取出来与右括号进行匹配
if (paren_map[c] != stack.pop()) {
return false;
}
}
return stack.length == 0;
};展开 
2019-05-24leetcode有点神奇啊，同样一份代码刷新一下页面再submit耗时会短一些，还有就是有些solution代码感觉和自己差不多，但是人家耗时就是更短，难道是我打开姿势不对嘛？
2019-05-12phper写的golang版本，看了下性能不好。
执行用时 : 16 ms, 在Valid Parentheses的Go提交中击败了12.87% 的用户
内存消耗 : 2 MB, 在Valid Parentheses的Go提交中击败了54.31% 的用户
func isValid(s string) bool {
var stack []byte
var sl = len(s)
for i:=0;i<sl;i++ {
l := len(stack)
if l == 0 {
stack = append(stack, s[i])
} else {
result := s[i] - stack[l-1]
fmt.Println(result)
if result>0 && result<3{
if len(stack) == 1 {
stack = []byte{}
continue
}
//出栈
stack = stack[:l-1]
} else {
// 压栈
stack = append(stack, s[i])
}
}
}
return len(stack) == 0
}展开作者回复: 帅