Leetcode之有效的括弧
- 2019 年 10 月 4 日
- 筆記
點擊上方 毛利學python，選擇置頂或星標
第一時間送達Python 技術乾貨！
我經常逛leetcode，決定每周更新幾道leetcode的題目
- 參考極客時間前facebook超哥和前google王爭
想購買的找我拿海報
- leetcode大神題解
有效的括弧
leetcode 第20題 判斷有效的括弧
我想到的左右消除，利用字典的對應關係來左括弧和右括弧相消，如果為空就是真。
class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ stack = [] map = {')':'(',']':'[','}':'{'} for i in s: # 出現了右括弧就不添加 if i not in map: stack.append(i) elif not stack or map[i] != stack.pop(): return False return not stack
當然還有堆棧的方法
class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ left = '{[(' rigth = '}])' mylist= [] for i in s: if i in left: mylist.append(i) # 說明就是右括弧 # 出現了右括弧沒有左括弧 出現了不對應的左括弧，如果有就刪到 elif len(mylist) == 0 or left.index(mylist.pop()) != rigth.index(i): return False return len(mylist) == 0
Java程式碼
class Solution { //3 ms, public boolean isValid(String s) { // 定義一個棧 Stack<Character> stack = new Stack<>(); for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); // || 或 如果是左括弧就push if(ch == '(' || ch == '{' || ch == '['){ stack.push(ch); }else{ // 現在是右括弧 if(stack.isEmpty()){ return false; } // 定義刪除的pop char pop = stack.pop(); // 三種可能 if(ch == ')' && pop != '('){ return false; }else if(ch == '}' && pop != '{'){ return false; }else if(ch == ']' && pop != '['){ return false; } } } return stack.isEmpty(); } }
js
js參考大神的題解
/** * @param {string} s * @return {boolean} */ var isValid = function (s) { //定義一個map var map = { "(": ")", "[": "]", "{": "}" } while (s.length) { var left = s[0]; if (!(left in map)) return false; var i = 1; while (s[i] != map[left] && i < s.length) left = s[i++]; if (s[i] != map[left]) return false s = s.slice(0, i - 1) + s.slice(i + 1, s.length); } return true };
