LeetCode quiz series -- 678. Valid bracket strings

Given a string containing only three characters: ( , ) and *, write a function to check if the string is a valid string.Valid strings have the following rules:

Any opening parenthesis (must have a corresponding closing parenthesis ).
Any closing bracket) must have a corresponding opening bracket ( .
A opening bracket (must precede the corresponding closing bracket).
* can be treated as a single closing bracket) , or a single opening bracket ( , orAn empty string.
An empty string is also considered a valid string.
Example 1:

Input: "()"
Output: True
Example 2:

Input: "(*)"
Output: True
Example 3:

Input: "(*))"
Output: True

Source: LeetCode
Link: https://leetcode.cn/problems/valid-parenthesis-string

Thinking:

1. Define two stacks, denoted as stack_a and stack_b respectively.2. Traverse the string:2.1) When the character is ( , push the current position index of the character into stack_a2.2) When the character is *, push the current position index of the character into stack_b2.3) When the character is ),If stack_a is not empty, pop the top element of stack_a; (try to match the left parenthesis first)If stack_a is empty and stack_b is not empty, the top element of stack_a will be popped; (when the left parentheses are no longer matched, continue to match *, because * no matter how many are left)If stack_a is empty and stack_b is empty, it means that there is no '(' or '*' matching ')' , indicating that the string does not meet the requirements, return false3. If stack_a is not empty:Then pop up the top of stack_a, and compare it with the top element of stack_b. If the value of the top of stack_b is larger than that of stack_a, it means that the index with the * character is behind the ( , which can form valid parentheses;Otherwise, if the string does not meet the requirements, return false

java:

class Solution {public boolean checkValidString(String s) {boolean result = true;Stack stackA = new Stack<>();Stack stackB = new Stack<>();for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {stackA.push(i);} else if (s.charAt(i) == '*') {stackB.push(i);} else {if (!stackA.empty()) {stackA.pop();} else if (!stackB.empty()) {stackB.pop();} else {// The current character is a right parenthesis, and there is no ( or * corresponding to it on the left side, indicating that a valid parenthesis cannot be formedreturn false;}}}// Obviously if the number of ( is less than * , then it must be invalid parenthesesif(stackA.size()>stackB.size()) {return false;}// if ( is left, then match *while (!stackA.empty() && !stackB.empty()) {if(stackA.peek()