GO语言实现： 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 }

作者回复: 👍🏻👍🏻👍🏻

2018-12-11



5

上神梵修

如果用对称数组思想会不会更好呢：如果为奇数直接false，为偶数则从中间向两边遍历对比。这样时间复杂度最大也只是n/2

作者回复: ()(())

2018-11-26



4

熙桐么么哒

想不到啊，如果没看过，根本想不到

作者回复: 对的，这个题目的解法，不管算法本身上，还是写出来的程序代码，都比较给人启示。

2018-10-12



3

Null

swift 版本 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;

2019-03-28



2

小天宇风

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; } }

作者回复: 帅！

2019-02-16



2

李超

C 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; }

作者回复: 赞👍🏻👍🏻

2019-01-03

3

2

unden

第二种方法的空间复杂度是不是O(n^2)?

作者回复: 对的，就是 O(n^2)

2018-10-12



1

余光

JavaScript搬 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-22





收起评论