1, 题目

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

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 注意空字符串可被认为是有效字符串。

示例 1:

  1. 输入: "()"
  2. 输出: true

示例 2:

  1. 输入: "()[]{}"
  2. 输出: true

示例 3:

  1. 输入: "(]"
  2. 输出: false

示例 4:

  1. 输入: "([)]"
  2. 输出: false

示例 5:

  1. 输入: "{[]}"
  2. 输出: true

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

2, 算法

1, stack的典型应用

  1. #python 实现
  2. class Solution:
  3.     def isValid(self, s: str) -> bool:
  4.         if not s:
  5.             return True
  6.         d = {
  7.             '(': 1,
  8.             '[': 2,
  9.             '{': 3,
  10.             ')': -1,
  11.             ']': -2,
  12.             '}': -3
  13.         }
  14.         left = ['(', '[', '{']
  15.         stack = []
  16.         for c in s:
  17.             if c in left:
  18.                 stack.append(c)
  19.             else:
  20.                 if not stack:
  21.                     return False
  22.                 else:
  23.                     x = stack.pop()
  24.                     if d[x] + d[c] != 0:
  25.                         return False
  26.         return len(stack) == 0
#scala 实现
object Solution {
    def isValid(s: String): Boolean = {
        if (s.isEmpty) {
            return true
        }
        val map = Map(
            '(' -> 1,
            ')' -> -1,
            '[' -> 2,
            ']' -> -2,
            '{' -> 3,
            '}' -> -3
        )
        val left = List('(', '[', '{')
        val stack = scala.collection.mutable.ArrayStack[Char]()
        for (c <- s) {
            if (left.contains(c)) {
                stack.push(c)
            } else if (stack.isEmpty) {
                return false
            } else {
                val x = stack.pop()
                if (map(x) + map(c) != 0) {
                    return false
                }
            }
        }
        stack.isEmpty
    }
}