Check for valid parentheses nesting

I found this question on leetcode and that was my answer ... But someone told me it's too bad that it takes \$O(n^3)\$ I am not sure that it takes all that time ... and trying to find better understandable Javascript solution.


Given a string containing just the characters '(', ')', '{', '}', '['
and ']', determine if the input string is valid. The brackets must
close in the correct order, "()" and "()[]{}" are all valid but "(]"
and "([)]" are not.



`/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
while (s.length != 0 && s.includes("[]") || s.includes("()") || s.includes("{}")) {
s = s.replace("[]", "");
s = s.replace("()", "");
s = s.replace("{}", "");
}
return s.length

Your friend's assertion that it's \$O(n^3)\$ is questionable. For that to be true, either or both of the replace or includes function needs to be \$O(n^2)\$ which is ... unlikely. It's more likely that both are \$O(mn)\$ complexity where m is the length of the source string, and n is the length of the search string ([] or {} or () all of which are "short")

Putting aside the complexity, it is still apparent that your code is not very efficient, even at \$O(n^2)\$.

An \$O(n)\$ solution is possible if you use a state machine and a stack (or recursion) to control the assertions. After any open parenthesis only 4 characters can follow, another open parenthesis ((, [, or {), or the matching close parenthesis. You can simplify the state machine by adding a dummy character, I'll use a . period to illustrate:



const terminator = ".",
openers = "{[(",
following = {
"[": "]",
"{": "}",
"(": ")",
};

/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {

// add terminating character.
s = s + terminator;

// seed stack with
const stack = [terminator];

for (const c of s) {
if (openers.includes(c)) {
// going deeper in to nesting.
stack.push(following[c]);
} else {
// coming out of nesting, check the correct closer.
// (which may be a "." at the end)
if (stack.pop() != c) {
return false;
}
}
}
return true;

};

console.log(isValid("({(())})")); // True
console.log(isValid("({((}))})")); // False

StackExchange Code Review Q#155552, answer score: 6