Topic link

Double stack method

Train of thought

Just to simplify things a little bit, if this problem didn’t have * and only had (,), it would only take one stack to do it.

  1. Create a stack to store(
  2. Traverses the string if the current character is(If the current character is)And if the stack is not empty, it pushes one stack(
  3. If the stack is empty at the end, prove that all parentheses match and are a valid parenthesis string

() () () () () () () () () () () () A stack has only two operations, on and off the stack, can only solve the characters that can be matched in a queue. Now we have added an indeterminate * character, obviously, one stack is not enough. If one is not enough, use two.

  1. Create two stacks, one for storage(One for storage*
  2. Iterating through the string, encountered(and*I’m going to go to the corresponding stack, and notice that I’m pushing the subscript, because I’m going to use it later
  3. encounter), consume first (out of stack)(The stack is exhausted and then consumed again*If both stacks are empty, then no sum can be added)Matches the character, then returns directlyfalse
  4. After the traversal is complete, both stacks may still have data*As a(and)Match,*The rest of the stack*To be a)and(Matches in the stack
  5. Because it’s two different stacks, there’s no guarantee of order, so you have to use subscripts because*As a)The,)Want to be in(In the back, so if*The subscript ratio stored at the top of the stack(If the top of the stack is large, the proofs are out of order and are returned directlyfalse
  6. The last to see(If the stack is empty, all matches are proved, and returnstrueOtherwise an invalid string is returnedfalse.

Finally, why look (stack is not empty?

* Can be empty string, does not matter whether there are many, as long as (can match the line

The illustration

Test case: “((*(**))”, result should return true

code

function checkValidString(s: string) :boolean {
    const leftBracketsStack = []; / / "(" stack
    const starStack = []; / / "*" stack

    for (let i = 0; i < s.length; i++) {
        const elem = s[i];
        if (elem === '(') {
            leftBracketsStack.push(i);
        } else if (elem === The '*') {
            starStack.push(i);
        } else {
            if (leftBracketsStack.length > 0) {
                leftBracketsStack.pop(); // when ")" is encountered, cancel "(" stack "("
            } else if (starStack.length > 0) {
                starStack.pop(); // Then cancel the "*" of the "*" stack as "("
            } else {
                return false; // No cancelling "(", return false}}}/ / the rest of the "*" as ") "and" (" offset, so make sure the pop-up "*" subscript than "(", is" () "such a match, rather than such") ("
    while (leftBracketsStack.length > 0 && starStack.length > 0) {
        if (leftBracketsStack.pop() > starStack.pop()) return false;
    }

    return leftBracketsStack.length > 0 ? false : true; // Finally all "(" should be cancelled out to be valid
};
Copy the code

Two-way comparison method

Train of thought

If a string is valid, it matches exactly from the left as well as from the right. (I don’t know how to prove this.)

code

function checkValidString(s: string) :boolean {
    let left = 0, right = 0;

    for (let i = 0; i < s.length; i++) {
        left += s[i] === ') ' ? -1 : 1; // From the left
        right += (s[s.length - 1 - i] === '(')? -1 : 1; // From the right

        if (left < 0 || right < 0) return false;
    }
    return true;
};
Copy the code

In fact, +1 and -1 can also be regarded as two operations on and off the stack, left and right can be regarded as two stacks

function checkValidString(s: string) :boolean {
    let left = [], right = [], leftTop = true, rightTop = true;

    for (let i = 0; i < s.length; i++) {
        // Start from the left
        if (s[i] === ') ') {
            leftTop = left.pop();
        } else {
            left.push(true);
        }
        // Start from the right
        if (s[s.length - 1 - i] === '(') {
            rightTop = right.pop();
        } else {
            right.push(true);
        }
        // There is no match in the stack, it is an invalid string
        if(! leftTop || ! rightTop)return false;
    }
    return true;
};
Copy the code

Dynamic programming

The idea of dynamic planning is explained in a word: small things, small things. Find the pattern, cache all the solutions from small to large, and then figure out the final solution.

If you don’t know anything about dynamic programming, check out the following two articles:

  • Comics: What is Dynamic programming?
  • Farewell to dynamic programming, even brush 40 questions, I summed up these routines, do not understand you hit me (ten thousand words long article)

Train of thought

  • Juejin. Cn/post / 684490…).

The more characters you have, the more things you need to consider when determining whether a string is a valid parenthesis string.

You can split a string into a substring, for example, if you have a string of length 4 (()), and if you want to ensure that the interval [0, 3] is a valid parenthesis string, you only need to ensure that 0 and 3 form parentheses and that the interval [1, 2] is a valid string. This is just one case, but there are other cases.

But here we see that we need a data structure to represent this interval, and when we iterate, we start with the smallest interval.

Here we can define a two-dimensional array: d[I][j] indicates whether the [I, j] subinterval of the string is a valid parenthesis string

  • [i, j]Is a valid string:d[i][j] = true
  • [i, j]Not a valid string:d[i][j] = false

Through:

// length indicates the length of the target string
for (let len = 0; len < length; len++) { // The string is traversed in the range of len each time
  for (let i = 0; i < length - len; i++) {
    letj = i + len; }}Copy the code

Let’s draw a graph to see how it works:

It is not hard to see that the string interval we are iterating over here is getting larger and larger, so in the end dp[0][s.length-1] is the result we want.

And finally, let’s look at what the rules and boundaries of minimum sets are

  • Rule: If you want intervals[i, j]Is a valid parenthesis string, and there are two cases:
    1. The current intervaldp[i][j]fortrueAnd his subintervaldp[i + 1][j - 1]Also for thetureExample:(())
    2. The current intervaldp[i][j]fortrueAnd you can find one insidek, made bykTwo truncated intervalsdp[i][ k]anddp[k+1][j]Also for thetrueExample:() ()
  • Boundary: is the case of the smallest granularity, that is, the string has only one character, when the character is*The value is valid; otherwise, the value is invalid

code

function checkValidString(s: string) :boolean {
    const { length } = s;
    // Initialize the dp array
    const dp: boolean[] [] =Array.from(new Array(length), x= > new Array(length).fill(false));

    for (let len = 0; len < length; len++) { // The string is traversed in the range of len each time
        for (let i = 0; i < length - len; i++) {
            let j = i + len;

            // 1. If the range is 0, the string has only one character
            if (len === 0) {
                dp[i][j] = s[i] === The '*'; // True when the current character is * because * is omnipotent
                continue;
            }

            // 2. If the first character of the current interval is an open parenthesis, and the last character is a close parenthesis
            if ((s[i] === '(' || s[i] === The '*') && (s[j] === ') ' || s[j] === The '*')) {
                // If the range is 1, return true, otherwise the subrange is valid
                dp[i][j] = (len === 1)?true : dp[i + 1][j - 1];
            }

            [I, k] and [k+1,j], truncated by k, form valid strings
            for (let k = i; k < j; k++) {
                dp[i][j] = dp[i][j] || (dp[i][k] && dp[k + 1][j]);

                if (dp[i][j] === true) {
                    break; }}}}return dp[0][length - 1];
};
Copy the code

Greedy algorithm

The idea of greedy algorithm is very simple, can be greedy for the biggest greedy, can not be greedy to settle for the next, and so on.

That is, every time we find a local optimal solution, we finally form a global optimal solution.

However, sometimes the local optimal solution does not guarantee that the final global solution is optimal, so the greedy difficulty is how to judge whether this algorithm can be used.

Train of thought

We can determine if the string is valid by counting the number of (.

Here because * can be omnipotent, greed, there are two cases:

  • If you can be greedy, take it*when(
  • It really can’t, and(When the number is not zero)

code

function checkValidString(s: string) :boolean {
    let min = 0; // The smallest possible number of open parentheses
    let max = 0; // The largest possible number of open parentheses

    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        
        // In the case of an open parenthesis, the largest and smallest numbers are incremented by one
        if (c === '(') {
            min++;
            max++;
        } else if (c === The '*') {
            // If it matches, subtract 1
            if(min ! = =0) min--;
            // The maximum number, every time the * is treated as an open parenthesis, so increment 1
            max++;
        } else {
            // If it matches, subtract 1
            if(min ! = =0) min--;
            // If the maximum number of parentheses is less than 0, then we can return false
            if (--max < 0) return false; }}return min === 0; // If it is valid, the last minimum number must be exactly matched
};
Copy the code

DFS

Train of thought

Count the number of open parentheses using stacks or numbers, and consider three cases where * is encountered

  • As a(
  • As a)
  • Empty string

You only need one of them to be true

The illustration

It’s a depth-first traversal of a tree.

code

function checkValidString(s: string, start: number = 0, count: number = 0) :boolean {
    if (count < 0) return false; // If the number of open parentheses is less than 0, return false

    for (let i = start; i < s.length; i++) {
        const c = s[i];

        if (c === '(') {
            count++;
        } else if (c === ') ') {
            if (count-- === 0) return false; // No open parenthesis cancels, return false
        } else {
            return checkValidString(s, i + 1, count + 1) | |/ / as a "("
                checkValidString(s, i + 1, count - 1) | |// as ")", cancel out a "("
                checkValidString(s, i + 1, count); / / as a ""}}return count === 0; // It is valid if the match ends just right
};
Copy the code

Note 📢 : this solution is not AC, meet “* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *” the test case when the timeout, reduce the number of *, the answer is right. We don’t have AC, but we can learn this idea