Question

20. 有效的括号

English Version

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

 

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解法

方法一：栈

遍历括号字符串 $s$，遇到左括号时，压入当前的左括号；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否匹配，若不匹配，直接返回 false。

也可以选择遇到左括号时，将右括号压入栈中；遇到右括号时，弹出栈顶元素（若栈为空，直接返回 false），判断是否是相等。若不匹配，直接返回 false。

两者的区别仅限于括号转换时机，一个是在入栈时，一个是在出栈时。

遍历结束，若栈为空，说明括号字符串有效，返回 true；否则，返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为括号字符串 $s$ 的长度。

class Solution:
  def isValid(self, s: str) -> bool:
    stk = []
    d = {'()', '[]', '{}'}
    for c in s:
      if c in '({[':
        stk.append(c)
      elif not stk or stk.pop() + c not in d:
        return False
    return not stk

class Solution {
  public boolean isValid(String s) {
    Deque<Character> stk = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
      if (c == '(' || c == '{' || c == '[') {
        stk.push(c);
      } else if (stk.isEmpty() || !match(stk.pop(), c)) {
        return false;
      }
    }
    return stk.isEmpty();
  }

  private boolean match(char l, char r) {
    return (l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']');
  }
}

class Solution {
public:
  bool isValid(string s) {
    string stk;
    for (char c : s) {
      if (c == '(' || c == '{' || c == '[')
        stk.push_back(c);
      else if (stk.empty() || !match(stk.back(), c))
        return false;
      else
        stk.pop_back();
    }
    return stk.empty();
  }

  bool match(char l, char r) {
    return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');
  }
};

func isValid(s string) bool {
  stk := []rune{}
  for _, c := range s {
    if c == '(' || c == '{' || c == '[' {
      stk = append(stk, c)
    } else if len(stk) == 0 || !match(stk[len(stk)-1], c) {
      return false
    } else {
      stk = stk[:len(stk)-1]
    }
  }
  return len(stk) == 0
}

func match(l, r rune) bool {
  return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}')
}

const map = new Map([
  ['(', ')'],
  ['[', ']'],
  ['{', '}'],
]);

function isValid(s: string): boolean {
  const stack = [];
  for (const c of s) {
    if (map.has(c)) {
      stack.push(map.get(c));
    } else if (stack.pop() !== c) {
      return false;
    }
  }
  return stack.length === 0;
}

use std::collections::HashMap;

impl Solution {
  pub fn is_valid(s: String) -> bool {
    let mut map = HashMap::new();
    map.insert('(', ')');
    map.insert('[', ']');
    map.insert('{', '}');
    let mut stack = vec![];
    for c in s.chars() {
      if map.contains_key(&c) {
        stack.push(map[&c]);
      } else if stack.pop().unwrap_or(' ') != c {
        return false;
      }
    }
    stack.len() == 0
  }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stk = [];
  for (const c of s) {
    if (c == '(' || c == '{' || c == '[') {
      stk.push(c);
    } else if (stk.length == 0 || !match(stk[stk.length - 1], c)) {
      return false;
    } else {
      stk.pop();
    }
  }
  return stk.length == 0;
};

function match(l, r) {
  return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');
}

public class Solution {
  public bool IsValid(string s) {
    Stack<char> stk = new Stack<char>();
    foreach (var c in s.ToCharArray()) {
      if (c == '(') {
        stk.Push(')');
      } else if (c == '[') {
        stk.Push(']');
      } else if (c == '{') {
        stk.Push('}');
      } else if (stk.Count == 0 || stk.Pop() != c) {
        return false;
      }
    }
    return stk.Count == 0;
  }
}

# @param {String} s
# @return {Boolean}
def is_valid(s)
  stack = ''
  s.split('').each do |c|
  if ['{', '[', '('].include?(c)
    stack += c
  else
    if c == '}' && stack[stack.length - 1] == '{'

    stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
    elsif c == ']' && stack[stack.length - 1] == '['
    stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
    elsif c == ')' && stack[stack.length - 1] == '('
    stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
    else
    return false
    end
  end
  end
  stack == ''
end

class Solution {
  /**
   * @param string $s
   * @return boolean
   */

  function isValid($s) {
    $stack = [];
    $brackets = [
      ')' => '(',
      '}' => '{',
      ']' => '[',
    ];

    for ($i = 0; $i < strlen($s); $i++) {
      $char = $s[$i];
      if (array_key_exists($char, $brackets)) {
        if (empty($stack) || $stack[count($stack) - 1] !== $brackets[$char]) {
          return false;
        }
        array_pop($stack);
      } else {
        array_push($stack, $char);
      }
    }
    return empty($stack);
  }
}