Topic describes

/ / 20. Effective brackets / / given a include only '(',') ', '{','} ', '/', ' 'the string s, determine whether a string is effective. // A valid string must meet the following requirements: // The left parenthesis must be closed with the same type of the right parenthesis. // The left parentheses must be closed in the correct order.Copy the code

Answer key

If s is null, or the length is odd, then false. Char [] STRS = char[] STRS = STRS // Since the parentheses of STRS are []() and [()], // there are also two combinations [()]{}. We can only cling to the point that the match of the traversed right parenthesis must be the left // parenthesis of the previous traversal. And this feature just fits the rules of the stack. If s is closed correctly, the left parenthesis must match the left parenthesis. If s is not closed correctly, the left parenthesis must match the left parenthesis. If s is not closed correctly, the left parenthesis must match the left parenthesis. Therefore, we also need to construct a matching relation table to match the left and right parentheses. // Create a HashMap called a map and store the parenthesis relationship. We want the resulting parenthesis // to be matched directly with the corresponding parenthesis when iterating through the parentheses. Since we store the open parentheses in the stack (the first one is left) // so we need to match the open parentheses, we store the close parentheses as key and the corresponding open parentheses as value in the map. // // iterates through STRS from left to right with STRS [I]. If STRS [I] is not in the map key, // it is an open parenthesis and stored in the stack. Check if the stack is empty (except STRS with // all close parentheses). // If STRS [I] matches the parenthesis // in the map, the match is successful, and the traversal continues. Otherwise, simply false. // When the loop ends, the stack is empty (if all STRS are left parentheses). // // execution time: 2 ms, beat 76.11% of users in all Java commits // Memory consumption: 36.9 MB, beat 10.83% of users in all Java commits import java.util.hashmap; import java.util.Stack; class Solution { public boolean isValid(String s) { int len = s.length(); if (s == null || len == 0 || len % 2 == 1) return false; Stack<Character> stack = new Stack<>(); char[] strs = s.toCharArray(); HashMap<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put(']', '['); map.put('}', '{'); for (int i = 0; i < len; i++) { if (! map.containsKey(strs[i])) stack.push(strs[i]); else { if (stack.isEmpty()) return false; Character temp = stack.pop();  if (!temp.equals(map.get(strs[i]))) return false; } } return stack.isEmpty(); } }Copy the code