This article is participating in the nuggets team online activity, click to see the details

I. Title Description:

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

  • Any open parenthesis(There must be a corresponding close parenthesis).

  • Any close parenthesis)There must be a corresponding open parenthesis( .

  • Left parenthesis (Must precede the corresponding close parenthesis).

  • * Can be viewed as a single close parenthesis ), or a single open parenthesis(, or an empty string.
  • An empty string is also considered a valid string.

Example 1:

Input: s = () Output: true

Example 2:

Input: s = (*) Output: true

Example 3:

Input: s = (*)) Output: true

Tip:

The string size will be in the range of [1,100]

Ii. Analysis of Ideas:

They add a twist to 20 by introducing *, which can be used instead of (or) or empty.

Step one:

We can introduce two stacks of stack and star, saving (and *, by iterating through the string, will) to match the two stacks.

  • Pop () = pop(); pop() = pop();
  • Stack if no, match star, star executes pop();
  • Return false if there is neither.

Example 1:

s = (*))

Finally, the stack stack length is 0, indicating that the matching requirements are met.

Step 2:

Match redundant (. After string traversal, possible stack and star stack lengths exist. At this point, we also need to judge the stack and star after the match. We can find the ones that don’t match, and return true if they do. Not conforming to:

  • If the star length is smaller than star, it indicates that*Not enough to fill(, direct non-conformity;
  • If the star length is greater than or equal to stack, the value can be met(Pairing.
    • Special circumstances:* (, we should adjust the method to divide the subscripts in S between the two stacks. In this case, determine the values of the two top elements of the stack whenstar.pop() < stack.pop()Is not in line with the conditions.

Example 2:

s = (*())(*((**()

After step 1 is matched, the length of both stack and star is not zero, and the length of star is greater than that of stack.In this case, you need to determine the value of the top element of the stack. Loop through both stacks, compare the tops of the stacks,star.pop() < stack.pop()Returns false. Stop the loop when the stack length is empty.

Iii. AC Code:

function checkValidString(s: string) :boolean {
    let stack = [];
    let star = [];
    for (let i = 0; i < s.length; i++) {
        switch (s[i]) {
            case "(":
                stack.push(i);
                break;
            case "*":
                star.push(i);
                break;
            case ")":
                if (stack.length) {
                    stack.pop();
                } else if (star.length) {
                    star.pop();
                } else {
                    return false;
                }
                break; }}if (star.length >= stack.length) {
        while (star.length && stack.length) {
            if (star.pop() < stack.pop()) return false; }}else {
        return false;
    }
    return true;
};
Copy the code

Iv. Summary:

To expand on the basis of the previous question, the stack is also used to save (and * respectively, and then match, mainly to find the relationship between the two stacks and S, and also to consider the existence of special cases.