## 20. 有效的括號 * 題目難度：簡單 * 源碼地址：https://gitee.com/mgang/leet-code/blob/master/java/src/main/java/com/mango/leet/code/easy/LC20_ValidParentheses.java ~~~ package com.mango.leet.code.easy; /** * 20. 有效的括號 */ import java.util.Stack; /** * 給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串 s ，判斷字符串是否有效。 * * 有效字符串需滿足： * * 左括號必須用相同類型的右括號閉合。 * 左括號必須以正確的順序閉合。 * ? * * 示例 1： * * 輸入：s = "()" * 輸出：true * 示例?2： * * 輸入：s = "()[]{}" * 輸出：true * 示例?3： * * 輸入：s = "(]" * 輸出：false * 示例?4： * * 輸入：s = "([)]" * 輸出：false * 示例?5： * * 輸入：s = "{[]}" * 輸出：true * ? * * 提示： * * 1 <= s.length <= 104 * s 僅由括號 '()[]{}' 組成 * * 來源：力扣（LeetCode） * 鏈接：https://leetcode-cn.com/problems/valid-parentheses * 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */ public class LC20_ValidParentheses { public static void main(String[] args) { System.out.println((int)'('); System.out.println((int)')'); System.out.println((int)'{'); System.out.println((int)'}'); System.out.println((int)'['); System.out.println((int)']'); System.out.println(new Solution().isValid("(){}}{")); } static class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack(); for(int i=0;i<s.length();i++){ if(stack.isEmpty()){ stack.push(s.charAt(i)); continue; } char c = s.charAt(i); Character character = stack.pop(); if(character == ']' || character == '}' || character == ')'){ return false; } if((character == '[' && c == ']') || (character == '{' && c == '}') || (character == '(' && c == ')')){ // 括號匹配，并且左括號在前 }else{ stack.push(character); stack.push(c); } } return stack.isEmpty(); } public boolean isValid2(String s) { Stack<Character> stack = new Stack(); for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(c == '['){ stack.push(']'); }else if(c == '{'){ stack.push('}'); }else if(c == '('){ stack.push(')'); }else if(!stack.isEmpty() && c != stack.peek()){ return false; }else { stack.pop(); } } return stack.isEmpty(); } // 自己用數組加下標模擬棧，不用api public boolean isValid3(String s) { int l = s.length(); char []st = new char[l]; int top = -1; for(int i = 0;i < l;i++){ char s_in = s.charAt(i); if(s_in == '(' || s_in == '[' || s_in == '{'){ top++; st[top] = s_in; } else{ if(top < 0){ return false; } if(s_in == ')' && st[top] != '('){ return false; } if(s_in == ']' && st[top] != '['){ return false; } if(s_in == '}' && st[top] != '{'){ return false; } top--; } } if(top > -1){ return false; } return true; } } } /** * 2022-03-02 * 思路： * 利用棧先入后出的特點，如果括號匹配就出站，不匹配且做括號在前的就先入棧 */ ~~~