Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.
An input string is valid if:
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
方法一：hashmap+栈
class Solution { public static boolean isValid(String s) { HashMap<Character,Character> map=new HashMap<Character,Character>(); Stack<Character> stack=new Stack<Character>(); map.put(‘)‘,‘(‘); map.put(‘]‘,‘[‘); map.put(‘}‘,‘{‘); int N=s.length(); char [] nums=s.toCharArray(); for(int i=0;i<N;i++){ if(!stack.isEmpty() && map.get(nums[i])==stack.peek()){ stack.pop(); }else{ stack.push(nums[i]); } } return stack.isEmpty() ? true :false; } }
方法二：栈
class Solution { public static boolean isValid(String s) { Stack<Character> stack=new Stack<Character>(); int N=s.length(); char [] nums=s.toCharArray(); for(int i=0;i<N;i++){ if(nums[i]==‘(‘||nums[i]==‘[‘||nums[i]==‘{‘){ stack.push(nums[i]); }else{ if(stack.isEmpty()){ return false; } int cr=stack.pop(); boolean a= cr==‘(‘ && nums[i]!=‘)‘; boolean b= cr==‘[‘ && nums[i]!=‘]‘; boolean c= cr==‘{‘ && nums[i]!=‘}‘; if(a||b||c){ return false; } } } return stack.isEmpty() ; } }
20. Valid Parentheses(用栈实现括号匹配)
原文：https://www.cnblogs.com/shaer/p/10859386.html