This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

Topic describes

Given a string s containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

A valid string must meet the following requirements:

1. Open parentheses must be closed with close parentheses of the same type. 2. The left parentheses must be closed in the correct order.

Input: s = "() [] {}" output: true input: s = "([]" output: false input: s = "{[]}" output: trueCopy the code

Thought analysis

The left parentheses must be closed in the correct order, which means that at least one pair of matches in the string must be joined together, like () {} [], so that it is closed in the correct order. If the left and right matches do not match, then it cannot be closed correctly, like (}).

This leads to a substitution approach, removing pairs of characters from the string and removing them over and over again until all pairs are gone. The replace method can be used to replace the empty string processing, {[()]}, first replace (), then {[]}, then {}, finally, the result is an empty string.

code

Use indexOf to determine if the corresponding string is contained, and then loop over and over again.

const isValid = function (s) {
    while (s.indexOf("()") > -1 || s.indexOf("[]") > -1 || s.indexOf("{}") > -1) {
        if (s.indexOf("()") > -1) {
            s = s.replaceAll("()", "");
        }
        if (s.indexOf("{}") > -1) {
            s = s.replaceAll("{}", "");
        }
        if (s.indexOf("[]") > -1) {
            s = s.replaceAll("[]", "");
        }
    }
    return s.length === 0;
};

Copy the code

Implementation-wise, there’s nothing wrong with this code, but speed wise, it’s not great.

Another way to do this is by iterating through the string, loading each left symbol into a temporary array stack, and each right symbol, one left symbol that matches, closes the last left symbol in the stack. It’s kind of like last in, first out of the stack, where the left of the last in gets matched first.

const isValid = function (s) { let map = { '{': '}', '(': ')', '[': ']' } let stack = [] for (let i = 0; i < s.length; I++) {if (map [s] [I]) {/ / had left, into an array of stack, push (s) [I]} else if (s [I]! == map[stack.pop()]) {return false}} return stack.length === = 0; };Copy the code

conclusion

Seemingly not difficult topic, in fact, or pretty around. There’s always a way to do it, but it’s just not that efficient.