使用JavaScript的有效Parentheses leetcode问题

Question

我正在尝试使用JavaScript从leetcode中找出有效的括号问题，但我无法想出如何解决这个问题的计划。

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

我目前的思维过程是这样的：

compare...?

• Not

• 将字符串拆分为数组(例如："{}“-> ["{”、"}“、"”)的

• 循环，通过数组

• 使用每个字符的索引来确定.

请帮帮忙。

Answer 1

下面是一个简单的堆栈实现：

​

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('{[)}'));

​

我首先为开始和结束括号创建两个查找对象。然后，这只是一个循环的问题，字符，和：

如果是开始括号，则将其推入堆栈；如果是结束括号，则从堆栈中弹出最后一个值，并检查其是否与结束括号匹配；在处理完所有内容后，检查堆栈是否为空。

• 。

Answer 2

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

const hasBalancedBrackets = text => !countUnmatchedBrackets(text)

function countUnmatchedBrackets(text) {
  return [...text].filter(isBracket).reduce((stack, bracket) =>
    isOpen(bracket) || !isMatch(stack.at(-1), bracket)
      ? /* push */ stack.concat(bracket)
      : /* pop  */ stack.slice(0, stack.length - 1), []).length
}

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

function isBracket(char) { return isOpen(char) || CLOSING_BRACKETS.includes(char) }
function isOpen(bracket) { return OPENING_BRACKETS.includes(bracket) }

[
  [false, '[){'],
  [true, 'a()a'],
  [true, '{{[([a]a)a]a}}'],
  [false, 'aa{a}a[aa(a](({[{a[[[()(([[a']
].forEach(([expected, input]) =>
  console.assert(expected === hasBalancedBrackets(input), input))

Answer 3

在Javascript中的有效部分(在许多采访中被问到)。(简单和可接受的解决办法)

这里使用的方法是string迭代和charAt以及替换方法。

var isValid = function(s) {
    let par ={'(' :')','{': '}', '[':']'};
    for(let i=0;i<s.length;++i) {
        if(s.charAt(i+1) && s.charAt(i+1)== par[s.charAt(i)]){
                s = s.replace(s.charAt(i)+s.charAt(i+1),'');
                i=i-2;
        }
    }
    if(s.length){
        console.log(false)
        return false;
    } else {
        console.log(true)
        return true;
    }
};
console.log(isValid("()[]{}"))