让我们一起啃算法----有效的括号

有效括号（Valid-Parentheses）

题干如下：

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
  1.左括号必须用相同类型的右括号闭合。
  2.左括号必须以正确的顺序闭合。
  3.注意空字符串可被认为是有效字符串。
示例 1:
  输入: “()”
  输出: true
示例 2:
  输入: “()[]{}”
  输出: true
示例 3:
  输入: “(]”
  输出: false
示例 4:
  输入: “([)]”
  输出: false
示例 5:
  输入: “{[]}”
  输出: true
来源：力扣

解题思路

这题是我大学老师教 栈 这种数据结构的应用场景时讲解的题目，稍微有一丢丢怀念。
解题思路很简单：从左到右遍历字符串，遇到 左括号: [ ( { ** 就压入栈中，遇到 **右括号: ] ) } 就拿 栈顶元素 与 当前元素 匹配，是否是一对括号。是，则继续遍历，不是，则直接返回 false。

注：
  1. 栈 是一种很常见的数据结构，特点是先进后出
  2. 栈顶元素 每次比较之后都要从栈中移除，即 pop 操作
  3. 为什么是遇到 左括号 将其压入栈中呢？假设我们将 右括号 压入栈中，由于我们是从左往右遍历的，当遇到 左括号 时假设我们取出栈顶元素 右括号 进行比较，这时候有一个问题：当前比较的 左括号 的位置其实是在 右括号 之后的，即类似 ][。
聪明的小伙伴一定猜到了，当我们从右向左遍历时，压入栈的就是 右括号 啦。

流程图如下：

代码实现

由于需要基于 栈 这种数据结构来解题，我简单用 go 实现了一个栈：

type Stack struct {
    stack []byte // 存放字节
    length int // 内部维护的长度
}

// 压栈
func (s *Stack) push(b byte) {
    s.stack = append(s.stack,b)
    s.length ++
}

// 出栈
func (s *Stack) pop() (res byte) {
    if s.length <= 0 {
        return
    }
    s.length --
    res = s.stack[s.length]
    s.stack = s.stack[0:s.length]
    return
}

// 判断栈是否为空
func (s *Stack) isEmpty() bool {
    return s.length <= 0
}

// 构造
func getStack() *Stack {
    return &Stack{
    }
}

下面的代码实现，基于上面的数据结构：

func isValid(s string) bool {
    if len(s) <= 0 {
        return true
    }
    // 实例化栈
    stack := getStack()
    for i := 0; i < len(s); i++ {
        // 判断是左括号就压入栈
        if s[i] == '(' || s[i] == '[' || s[i] == '{' {
            stack.push(s[i])
        } else {
            // 如果栈为空，这时候 i 没有越界，则返回 false
            if stack.isEmpty() {
                return false
            }
            // 获取栈顶元素
            top := stack.pop()
            // 比较是否匹配
            if '(' == top && s[i] != ')' || '[' == top && s[i] !=']' || '{' == top && s[i] !='}'{
                return false
            }
        }
    }
    // 如果 i 越界，并且 栈 为空，则返回 true
    if stack.isEmpty() {
        return true
    }
    return false
}

扩展思路

在用 栈 解题的过程中会发现： 如果字符串是有效括号，那么一
定存在一对相邻的括号，并且第一个匹配的右括号，左边的元素一定是
相对应的左括号。

基于上面的认知，我们将这对相邻的括号替换成空字符串，剩下的字符串，如果是有效字符串，仍会存在一对相邻的括号，同理再替换，依次循环。如果不存在一对相邻的括号，并且最后剩下的字符串为空了，那么原始字符串就是有效括号，否则不是。

流程图如下：

具体的代码实现如下：（ 只是提供一种思路，这种实现方式时间复杂度有点高 ）

func isValidOther(s string) bool {

   // 判断是否有一对相邻的括号
  for strings.Index(s,"()") != -1 || strings.Index(s,"[]") != -1 || strings.Index(s,"{}") != -1 {

      // 存在，则替换成 空字符串， 继续下次判断
  s = strings.Replace(s,"()","",-1)
      s = strings.Replace(s,"[]","",-1)
      s = strings.Replace(s,"{}","",-1)
   }

   // 如果不存在一对相邻的括号，并且剩余的字符串长度不为0，则返回 false
  if len(s) >= 1 {
      return false
  }
   return true
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-a...

本作品采用《CC 协议》，转载必须注明作者和本文链接