I'm trying to figure out valid parentheses problem from leetcode using JavaScript and I couldn't figure out a plan on how to solve this problem.

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.


Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

My current thinking process is like this:

1. Split the string into an array (example: "{}" --> ["{","}", "[", "]", "(", ")"]
2. Loop through the array
3. Use the index of each characters to compare...?
4. Not sure after this...

Help please.

CodePudding user response：

Here's a simple stack implementation:

const BRACKETS = [['(', ')'], ['[', ']'], ['{', '}']];
const OPEN = BRACKETS.reduce((a, [o, c]) => ({...a, [o]: c}), {});
const CLOSE = BRACKETS.reduce((a, [o, c]) => ({...a, [c]: o}), {});

const isBalanced = (s) => {
  const stack = [];
  
  for (const c of [...s]) {
    if (c in OPEN) stack.push(c);
    if (c in CLOSE && stack.pop() !== CLOSE[c]) return false;
  }
  
  return !stack.length;
};

console.log(isBalanced('{{[()]()}}'));
console.log(isBalanced('{[)}'));

I first create two lookup objects for opening and closing brackets. Then it's just a matter of looping over the characters, and:

• if it's an opening bracket, push it onto the stack;
• if it's a closing bracket, pop the last value off the stack and check whether it matches the closing bracket;
• after everything is processed, check that the stack is empty.

CodePudding user response：

const OPENING_BRACKETS = ['(', '[', '{'];
const CLOSING_BRACKETS = [')', ']', '}'];

function hasBalancedBrackets(text) {
    return isString(text)
        && text.length > 1
        && isEmpty(findUnmatchedBrackets(text));
}

function findUnmatchedBrackets(text) {
    return filter(text, isBracket).reduce((stack, bracket) =>
            isOpen(bracket) || !isMatch(peek(stack), bracket)
                ? push(stack, bracket)
                : pop(stack),
        []);
}

function isMatch(lastBracket, bracket) {
    return OPENING_BRACKETS.some((openBracket, i) =>
        lastBracket === openBracket &&
        bracket === CLOSING_BRACKETS[i]
    );
}

function isString(obj) { return toString(obj) === toString(''); }
function toString(obj) { return Object.prototype.toString.call(obj); }
function isEmpty(stack) { return stack.length === 0; }
function filter(obj, fn) { return Array.prototype.filter.call(obj, fn); }
function isBracket(char) { return isOpen(char) || inArray(CLOSING_BRACKETS, char); }
function isOpen(bracket) { return inArray(OPENING_BRACKETS, bracket); }
function inArray(arr, obj) { return arr.indexOf(obj) !== -1; }
function push(stack, obj) { return stack.concat(obj); }
function peek(stack) { return stack[stack.length - 1]; }
function pop(stack) { return stack.slice(0, stack.length - 1); }

console.log(hasBalancedBrackets("()"))
console.log(hasBalancedBrackets("()[]{}"))
console.log(hasBalancedBrackets("(]"))
console.log(hasBalancedBrackets("([{test}])"))
console.log(hasBalancedBrackets("([{{])"))