天天演算法 | Easy | 10. 有效括弧：Valid Parentheses

每天來一道，面試不卡殼，今天是天天演算法陪你成長的第10天

本題可在LeetCode上OJ，鏈接： Valid Parentheses

題目描述：

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]"are not.

題目翻譯

給出一個字元串僅包含如下字元(，)，{，}，[和]，判斷輸入的字元串是否有效。

所有括弧以正確的順序閉合該字元串即為有效，比如"()"和"()[]{}"都是有效的字元串，但是"(]"和"([)]"都是無效的字元串。

解題方案

標籤： String

思路：

使用棧結構來存儲，遍歷字元串，當出現 ( , { , [ 這三個字元的時候，將字元壓入棧中否則則代表出現的是 ) , } , ] 這三個字元當 ) , } , ] 這些字元時先判斷棧內是否為空，如果為空，說明沒有與之匹配的字元存在，則返回false。如果不為空，則判斷是否棧頂元素與當前出現的字元匹配，即是否滿足 () {} [] 兩兩匹配，如果不匹配則返回false。遍歷結束後如果棧內還有元素，說明匹配不完全，則返回false，如果為空則匹配完全，返回true。

代碼：

class Solution {n public boolean isValid(String s) {n Stack<Character> st = new Stack<Character>();n for(int i=0;i<s.length();i++){n if(s.charAt(i) == ( || s.charAt(i) == { || s.charAt(i) == [)n st.push(s.charAt(i));n else if(st.isEmpty() ||n s.charAt(i) == ) && st.pop() != ( || n s.charAt(i) == } && st.pop() != { || n s.charAt(i) == ] && st.pop() != [)n return false;n }n return st.size() == 0;n }n}n

參考資料 blog.csdn.net...

歡迎加入碼蜂社演算法交流群：天天一道演算法題

掃描下方二維碼或搜素「碼蜂社」公眾號，不怕錯過好文章：

推薦閱讀：