7
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.