valid-parentheses

2017-10-01
  • 匹配法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const isValid = (s) => {
  while (true) {
    let len = s.length;
    // 将字符串按照匹配对，挨个替换为 ''
    s = s.replace('{}', '').replace('[]', '').replace('()', '');
    // 有两种情况 s.length 会等于 len
    // 1. s 匹配完了，变成了空字符串
    // 2. s 无法继续匹配，匹配后的长度和和匹配前的长度一样（比如 "({]",一开始 len 是 3，匹配后还是 3，说明不用继续匹配了）
    if (s.length === len) {
      return len === 0;
    }
  }
};

const s = '{[()]}';
isValid(s);
1
2
3
4
5
6
const isValid = (s) => {
  while (s.includes('{}') || s.includes('[]') || s.includes('()')) {
    s = s.replace('{}', '').replace('[]', '').replace('()', '');
  }
  return s.length === 0;
};
  • 栈解法

解题信息中强调对称性，而栈（先入后出）入栈和出栈恰好是反着来，形成了鲜明的对称性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const isValid = (s) => {
  // 空字符串符合条件
  if (!s) {
    return true;
  }

  const leftToRight = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const stack = [];

  for (let i = 0, len = s.length; i < len; i++) {
    const ch = s[i];
    // 左括号
    if (leftToRight[ch]) {
      stack.push(ch);
    } else {
      // 右括号开始匹配
      // 1. 如果栈内没有左括号，直接 false
      // 2. 有数据但是栈顶元素不是当前的右括号
      if (!stack.length || leftToRight[ stack.pop() ] !== ch) {
        return false;
      }
    }
  }

  // 最后检查栈内还有没有元素，有说明还有未匹配则不符合
  return !stack.length;
};