Pengjielee's blog

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = "()"
输出：true

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

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true

提示：

1 <= s.length <= 10^4；
s 仅由括号 ‘()[]{}’ 组成；

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

我们遍历字符串中的所有字符：

1、如果遇到了左括号，就把对应的右括号压栈（比如遇到了字符’(’，就把字符’)‘压栈）。

2、如果遇到了右括号

查看栈是否为空，如果为空，说明不能构成有效的括号，直接返回false。
如果栈不为空，栈顶元素出栈，然后判断出栈的这个元素是否等于这个右括号，如果不等于，说明不匹配，直接返回false。如果匹配，就继续判断字符串的下一个字符。

3、最后如果栈为空，说明是完全匹配，是有效的括号，否则如果栈不为空，说明不完全匹配，不是有效的括号。

作者：数据结构和算法链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/?discussion=rj6XSA 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

参考1:

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const stack = [];
  const map = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  //遍历字符串
  for (let char of s) {
    //如果map结构中存在左括号，把左括号入栈
    if (char in map) {
      stack.push(char);
    } else {
      //不存在，
      //1. 如果栈为空，直接返回false
      //2. 如果当前字符 与 map[栈中左括号]存储的右括号不匹配，返回false
      if (!stack.length || char != map[stack.pop()]) {
        return false;
      }
    }
  }

  // 如果最后 stack 里没有元素了， 就一定是匹配的
  return !stack.length;
};

参考2:

var isValid = (s) => {
  const stack = [];

  //遍历所有的元素
  for (let c of s) {
    //如果是左括号，就把他们对应的右括号压栈
    if (c == "(") {
      stack.push(")");
    } else if (c === "{") {
      stack.push("}");
    } else if (c === "[") {
      stack.push("]");
    } else if (stack.length === 0) {
      //1. 如果栈为空，说明括号无法匹配。
      return false;
    } else if (stack.pop() != c) {
      //2. 如果栈不为空，栈顶元素就要出栈，和这个右括号比较。
      //如果栈顶元素不等于这个右括号，说明无法匹配，直接返回false。
      return false;
    }
  }

  //最后如果栈为空，说明完全匹配，是有效的括号。
  //否则不完全匹配，就不是有效的括号
  return stack.length === 0;
};

Go实现

package main

import "fmt"

type Stack struct {
  top  int           //栈顶指针
  data []interface{} //数据元素
}

func (s *Stack) InitList(maxSize int) {
  s.data = make([]interface{}, maxSize)
  s.top = -1
}

func (s *Stack) isNull() bool {
  if s.top != -1 {
    return false
  } else {
    return true
  }
}

func (s *Stack) isFull() bool {
  if s.top < cap(s.data)-1 {
    return false
  } else {
    return true
  }
}
func (s *Stack) Push(element interface{}) bool {
  if s.isFull() {
    return false
  }
  s.top++
  s.data[s.top] = element
  return true
}

func (s *Stack) Pop() (interface{}, bool) {
  if s.isNull() {
    return nil, false
  }
  e := s.data[s.top]
  s.top--
  return e, true
}

func test(str string) bool {
  s := Stack{}
  s.InitList(20)

  m := make(map[string]string, 3)
  m["("] = ")"
  m["{"] = "}"
  m["["] = "]"

  for i := 0; i < len(str); i++ {
    char := string(str[i])

    //如果是左括号, 入栈
    if m[char] != "" && !s.isFull() {
      s.Push(char)
    } else {
      //如果是右括号
      //判断是否栈空, 栈空匹配失败
      if s.isNull() {
        return false
      }
      //出栈
      if e, ok := s.Pop(); ok {
        if char != m[e.(string)] {
          return false
        }
      }
    }
  }

  if s.isNull() {
    return true
  } else {
    return false
  }
}

func main() {
  fmt.Println(test("()"))   //true
  fmt.Println(test("()"))   //true
  fmt.Println(test(")("))   //false
  fmt.Println(test("(()"))  //false
  fmt.Println(test("(())")) //true
}