1. Title Description

Second, train of thought analysis

2.1 analysis

Check whether the parentheses contained in the given string are valid.

  1. The first is to replace the string with an empty string as soon as the correct parentheses are found. If the string ends empty, the parentheses contained in the string are valid. However, this is very inefficient, and has a great impact on memory and time, for reference only.
  2. The second approach is to take advantage of the first-in, last-out nature of the stack. Iterate through each character of the string, pushing the left parentheses (‘(‘, ‘[‘, ‘{‘)) onto the stack. Pushing the top parentheses off the stack if the right parentheses (‘)’, ‘]’, ‘}’) are encountered. If the stack is found to be empty or mismatched, return false. If it matches, the next character of the string is iterated. Finally the string is iterated and the stack is empty, indicating that all parentheses match.

2.2 the illustration

  • Refer to Krahets valid brackets

Third, antithesis

Implementation of valid parentheses

  • Practice a
class Solution {
    public boolean isValid(String s) {
		while (s.contains("()") || s.contains("{}")
        || s.contains("[]")) {
            s = s.replace("()"."");
            s = s.replace("{}"."");
            s = s.replace("[]"."");
        }
        returns.isEmpty(); }}Copy the code
  • Approach 2
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // Fetch each character
            char ch = s.charAt(i);
            // The character is the left parenthesis, pushed into the stack
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }
            // The character extracted is the right half of the parenthesis
            if (ch == ') ' || ch == '] ' || ch == '} ') {
                // The current stack is empty, indicating no match
                if (stack.isEmpty()) {
                    return false;
                }
                // The stack is not empty, and the top bracket of the current stack is removed
                char top = stack.pop();
                // A mismatch occurs
                if (ch == ') '&& top ! ='(') {
                    return false;
                }
                if (ch == '] '&& top ! ='[') {
                    return false;
                }
                if (ch == '} '&& top ! ='{') {
                    return false; }}}returnstack.isEmpty(); }}Copy the code