Check for valid parentheses nesting

Question

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 < 1
};
console.log(isValid("({(())})")); // True
console.log(isValid("({((}))})")); // False

• Flambino: Here's a related question
• Mike Brant: Another similar question - codereview.stackexchange.com/questions/147259/…

Answer 1

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

• yeputons: Well, strictly speaking if it's \$O(n^2)\,ドル then it's also \$O(n^3)\$ and even \$O(2^n)\$ :)
• srgbnd: @yeputons could you please explain why?
• yeputons: @srgbnd \$f(n)=O(g(n))\$ is an assertion about upper bound on \$f(n)\$. It says "\$f(n)\$ grows not faster than \$g(n)\$", but \$f(n)\$ can grow even slower. You may want to look into \$\Theta(g(n))\$: stackoverflow.com/questions/471199