LeetCode 之 JavaScript 解答第20題 —— 有效的括號(Valid Parentheses)
Time:2019/4/11
Title: Valid Parentheses
Difficulty: Easy
Author: 小鹿
題目:Valid Parentheses
Given a string containing just the characters'('
,')'
,'{'
,'}'
,'['
and']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
給定一個只包括'('
,')'
,'{'
,'}'
,'['
,']'
的字串,判斷字串是否有效。
有效字串需滿足:
- 左括號必須用相同型別的右括號閉合。
- 左括號必須以正確的順序閉合。
注意空字串可被認為是有效字串。
Example 1:
Input: "()" Output: true
Example 2:
Input: "()[]{}" Output: true
Example 3:
Input: "(]" Output: false
Example 4:
Input: "([)]" Output: false
Example 5:
Input: "{[]}" Output: true
Solve:
▉ 演算法思路
1、首先,我們通過上邊的例子可以分析出什麼樣子括號匹配是複合物條件的,兩種情況。
{} [] { [ ( ) ] }
除去這兩種情況都不是符合條件的。
2、然後,我們將這些括號自右向左看做棧結構,右側是棧頂,左側是棧尾。
3、如果編譯器中的括號左括號,我們就入棧(左括號不用檢查匹配);如果是右括號,就取出棧頂元素檢查是否匹配。(提前將成對的括號通過鍵值對的方式存到散列表中)
4、如果匹配,就出棧。否則,就返回 false;
▉ 程式碼實現
下方程式碼在標準的 Leetcode 測試中並不是最省記憶體和效率高的,因為我們用到了 Map,在內
var isValid = function(s) { let stack = []; //將括號匹配存入散列表中 let map = new Map(); map.set(")","("); map.set("]","["); map.set("}","{"); // 取出字串中的括號 for(let i = 0; i < s.length; i++){ let c = s[i]; //如果是右括號,如果棧中不為空就出棧棧頂資料 if(map.has(c)){ //判斷棧此時是否為0 if(stack.length !== 0){ //如果棧頂元素不相同,就返回 false if(stack.pop() !== map.get(c)){ return false; } //如果此時棧內無元素,返回false }else{ return false; } }else{ //如果是左括號,就進棧 stack.push(c); } } //如果棧為空,括號全部匹配成功 return stack.length === 0; }; let str = "({(})"; console.log(isValid(str));
▉ 程式碼改進
2)在判斷時,沒有用到提前儲存的結構,直接使用當遇到左括號是直接入棧,提高了執行效率。
var isValid = function(s) { let stack = []; var obj = { "]": "[", "}": "{", ")": "(", }; for(var i = 0; i < s.length; i++) { if(s[i] === "[" || s[i] === "{" || s[i] === "(") { stack.push(s[i]); } else { var key = stack.pop(); if(maps[key] !== s[i]) { return false; } } } if(!stack.length) { return true; } return false; };
▉ 複雜度分析
空間複雜度:O(n)。當只有左括號近棧,沒有右括號進行匹配的時候是最糟糕的情況,所有括號都在棧內。例如:{{{{{{{{{
歡迎關注我個人公眾號:「一個不甘平凡的碼農」,記錄了自己一路自學程式設計的故事。
LeetCode 其他題目解析,Github:https://github.com/luxiangqia...