<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 0020. 有效的括號 ## 題目地址(20. 有效的括號) <https://leetcode-cn.com/problems/valid-parentheses/description> ## 題目描述 ``` <pre class="calibre18">``` 給定一個只包括 '(',')','{','}','[',']' 的字符串,判斷字符串是否有效。 有效字符串需滿足: 左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。 注意空字符串可被認為是有效字符串。 示例 1: 輸入: "()" 輸出: true 示例 2: 輸入: "()[]{}" 輸出: true 示例 3: 輸入: "(]" 輸出: false 示例 4: 輸入: "([)]" 輸出: false 示例 5: 輸入: "{[]}" 輸出: true ``` ``` ## 前置知識 - [棧](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 百度 - 騰訊 - 字節 - airbnb - amazon - bloomberg - facebook - google - microsoft - twitter - zenefits ## 棧 ### 思路 關于這道題的思路,鄧俊輝講的非常好,沒有看過的同學可以看一下,[視頻地址](http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184+sp/courseware/ad1a23c053df4501a3facd66ef6ccfa9/8d6f450e7f7a445098ae1d507fda80f6/)。 使用棧,遍歷輸入字符串 如果當前字符為左半邊括號時,則將其壓入棧中 如果遇到右半邊括號時,分類討論: 1)如棧不為空且為對應的左半邊括號,則取出棧頂元素,繼續循環 2)若此時棧為空,則直接返回 false 3)若不為對應的左半邊括號,反之返回 false ![](https://img.kancloud.cn/d7/3a/d73a226d8329befb1f16533545257b33_960x540.gif) (圖片來自: <https://github.com/MisterBooo/LeetCodeAnimation>) > 值得注意的是,如果題目要求只有一種括號,那么我們其實可以使用更簡潔,更省內存的方式 - 計數器來進行求解,而 不必要使用棧。 > > 事實上,這類問題還可以進一步擴展,我們可以去解析類似 HTML 等標記語法, 比如 ### 關鍵點解析 1. 棧的基本特點和操作 2. 如果你用的是 JS 沒有現成的棧,可以用數組來模擬 入: push 出:pop > 入: push 出 shift 就是隊列 ### 代碼 代碼支持:JS,Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {string} s * @return {boolean} */</span> <span class="hljs-keyword">var</span> isValid = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">let</span> valid = <span class="hljs-params">true</span>; <span class="hljs-keyword">const</span> stack = []; <span class="hljs-keyword">const</span> mapper = { <span class="hljs-string">"{"</span>: <span class="hljs-string">"}"</span>, <span class="hljs-string">"["</span>: <span class="hljs-string">"]"</span>, <span class="hljs-string">"("</span>: <span class="hljs-string">")"</span>, }; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i <span class="hljs-keyword">in</span> s) { <span class="hljs-keyword">const</span> v = s[i]; <span class="hljs-keyword">if</span> ([<span class="hljs-string">"("</span>, <span class="hljs-string">"["</span>, <span class="hljs-string">"{"</span>].indexOf(v) > <span class="hljs-params">-1</span>) { stack.push(v); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">const</span> peak = stack.pop(); <span class="hljs-keyword">if</span> (v !== mapper[peak]) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } } } <span class="hljs-keyword">if</span> (stack.length > <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">return</span> valid; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isValid</span><span class="hljs-params">(self,s)</span>:</span> stack = [] map = { <span class="hljs-string">"{"</span>:<span class="hljs-string">"}"</span>, <span class="hljs-string">"["</span>:<span class="hljs-string">"]"</span>, <span class="hljs-string">"("</span>:<span class="hljs-string">")"</span> } <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> s: <span class="hljs-keyword">if</span> x <span class="hljs-keyword">in</span> map: stack.append(map[x]) <span class="hljs-keyword">else</span>: <span class="hljs-keyword">if</span> len(stack)!=<span class="hljs-params">0</span>: top_element = stack.pop() <span class="hljs-keyword">if</span> x != top_element: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">continue</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">return</span> len(stack) == <span class="hljs-params">0</span> ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## O(1) 空間 ### 思路 基本思路是修改參數,將參數作為我們的棧。 隨著我們不斷遍歷, s 慢慢變成了一個棧。 因此 Python,Java,JS 等**字符串不可變**的語言無法使用此方法達到 O(1)O(1)O(1)。 具體參考: [No stack O(1) space complexity O(n) time complexity solution in C++](https://leetcode.com/problems/valid-parentheses/discuss/9478/No-stack-O(1)-space-complexity-O(n)-time-complexity-solution-in-C++/244061>) ### 代碼 代碼支持:C++ C++: ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isValid</span><span class="hljs-params">(<span class="hljs-params">string</span> s)</span> </span>{ <span class="hljs-keyword">int</span> top = <span class="hljs-params">-1</span>; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i =<span class="hljs-params">0</span>;i<s.length();++i){ <span class="hljs-keyword">if</span>(top<<span class="hljs-params">0</span> || !isMatch(s[top], s[i])){ ++top; s[top] = s[i]; }<span class="hljs-keyword">else</span>{ --top; } } <span class="hljs-keyword">return</span> top == <span class="hljs-params">-1</span>; } <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(<span class="hljs-keyword">char</span> c1, <span class="hljs-keyword">char</span> c2)</span></span>{ <span class="hljs-keyword">if</span>(c1 == <span class="hljs-string">'('</span> && c2 == <span class="hljs-string">')'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span>(c1 == <span class="hljs-string">'['</span> && c2 == <span class="hljs-string">']'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span>(c1 == <span class="hljs-string">'{'</span> && c2 == <span class="hljs-string">'}'</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } }; ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) ## 正則匹配 ### 思路 我們不斷通過消除 '\[\]' , '()', '{}' ,最后判斷剩下的是否是空串即可,就像開心消消樂一樣。 ### 代碼 代碼支持:Python,JavaScript Python: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isValid</span><span class="hljs-params">(self, s)</span>:</span> <span class="hljs-keyword">while</span> <span class="hljs-string">'[]'</span> <span class="hljs-keyword">in</span> s <span class="hljs-keyword">or</span> <span class="hljs-string">'()'</span> <span class="hljs-keyword">in</span> s <span class="hljs-keyword">or</span> <span class="hljs-string">'{}'</span> <span class="hljs-keyword">in</span> s: s = s.replace(<span class="hljs-string">'[]'</span>,<span class="hljs-string">''</span>).replace(<span class="hljs-string">'()'</span>,<span class="hljs-string">''</span>).replace(<span class="hljs-string">'{}'</span>,<span class="hljs-string">''</span>) <span class="hljs-keyword">return</span> <span class="hljs-keyword">not</span> len(s) ``` ``` JavaScript: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> isValid = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{ <span class="hljs-keyword">while</span> (s.includes(<span class="hljs-string">"[]"</span>) || s.includes(<span class="hljs-string">"()"</span>) || s.includes(<span class="hljs-string">"{}"</span>)) { s = s.replace(<span class="hljs-string">"[]"</span>, <span class="hljs-string">""</span>).replace(<span class="hljs-string">"()"</span>, <span class="hljs-string">""</span>).replace(<span class="hljs-string">"{}"</span>, <span class="hljs-string">""</span>); } s = s.replace(<span class="hljs-string">"[]"</span>, <span class="hljs-string">""</span>).replace(<span class="hljs-string">"()"</span>, <span class="hljs-string">""</span>).replace(<span class="hljs-string">"{}"</span>, <span class="hljs-string">""</span>); <span class="hljs-keyword">return</span> s.length === <span class="hljs-params">0</span>; }; ``` ``` **復雜度分析** - 時間復雜度:取決于正則引擎的實現 - 空間復雜度:取決于正則引擎的實現 ## 相關題目 - [32. 最長有效括號](32.longest-valid-parentheses.html) ## 擴展 - 如果讓你檢查 XML 標簽是否閉合如何檢查, 更進一步如果要你實現一個簡單的 XML 的解析器,應該怎么實現? 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看