# 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 < 1
};

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

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) {

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

• Well, strictly speaking if it's $O(n^2)$, then it's also $O(n^3)$ and even $O(2^n)$ :) – yeputons Feb 17 '17 at 4:15
• @yeputons could you please explain why? – srgbnd May 4 at 13:18
• @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 – yeputons May 5 at 20:38