有效的字符串

题目描述

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

有效字符串需满足：

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

测试用例

用例一

输入：s = “()”

输出：true

用例二

输入：s = “()[]{}”

输出：true

用例三

输入：s = “(]”

输出：false

用例四

输入：s = “([)]”

输出：false

用例五

输入：s = “{[]}”

输出：true

解题思路

一、字符串为空,认为匹配

二、字符串长度为奇数,一定不匹配

三、当前为左括号,入栈

四、当前为右括号, 弹出栈顶, 如何当前不匹配, 返回false

五、最终处理完成,栈为空,则括号完全匹配

代码实现

// isValid 判断是否为有效的字符串
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 10:57 下午 2021/2/9
func isValid(s string) bool {
  if len(s) == 0 {
    return true
  }

  if len(s)%2 == 1 {
    return false
  }

  // 括号标示的数据结构
  type charFlag struct {
    matchChar string
    isRight   bool
  }

  charTable := map[string]charFlag{
    "(": {isRight: false},
    ")": {isRight: true, matchChar: "("},
    "[": {isRight: false},
    "]": {isRight: true, matchChar: "["},
    "{": {isRight: false},
    "}": {isRight: true, matchChar: "{"},
  }
  waitMatchCharList := make([]string, 0)
  for _, c := range s {
    var (
      exist      bool
      charConfig charFlag
    )
    if charConfig, exist = charTable[string(c)]; !exist {
      continue
    }
    if !charConfig.isRight {
    // 左括号入栈
      waitMatchCharList = append(waitMatchCharList, string(c))
      continue
    }
    // 右括号匹配
    if len(waitMatchCharList) == 0 {
      // 栈已空，匹配失败
      return false
    }
    // 判断栈顶和当前括号是否匹配
    if waitMatchCharList[len(waitMatchCharList)-1] != charConfig.matchChar {
      // 括号不匹配
      return false
    }
    waitMatchCharList = waitMatchCharList[:len(waitMatchCharList)-1]
  }
  if len(waitMatchCharList) == 0 {
    // 完全匹配
    return true
  }

  return false
}