乐趣区

关于leetcode:Golang力扣Leetcode初级算法其他有效的括号

题目 :给定一个只包含 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 s,判断字符串是否无效。

提醒 :无效字符串需满足:

  • 左括号必须用雷同类型的右括号闭合。
  • 左括号必须以正确的程序闭合。

链接 :力扣 Leetcode—高级算法—其余—无效的括号.

示例 1

输出:s = “()”
输入:true

示例 2

输出:s = “()[]{}”
输入:true

示例 3

输出:s = “(]”
输入:false

示例 4

输出:s = “([)]”
输入:false

示例 5

输出:s = “{[]}”
输入:true

标签 :栈、字符串

思路 :要让所有的括号匹配,最容易想到的办法就是栈。遍历字符串,每读到一个左括号,便将其入栈;若呈现右括号,则匹配栈内的左括号,删除匹配过的左括号;当没有与右括相匹配的左括号,则该字符串不非法。如果读完字符串之后栈内仍有元素,阐明有多余的左括号,该字符串也不非法。

次要 Go 代码如下:

package main

import "fmt"

func isValid(s string) bool {var n = len(s)
    // 字符串的匹配,单字符类型为 byte
    myDick := map[byte]byte{']': '[',
        ')': '(',
        '}': '{',}
    // 如果字符串为空则返回 true
    if n == 0 {return true}
    // 创立切片充当栈
    var stack []byte
    // 遍历字符串中的元素
    for i := 0; i < n; i++ {
        // 如果以后字符是左括号,则存入栈内
        if (s[i] == '[') || (s[i] == '{') || (s[i] == '(') {stack = append(stack, s[i])
            // 若呈现右括号,则匹配栈内的左括号
        } else if len(stack) > 0 && stack[len(stack)-1] == myDick[s[i]] {
            // 删除匹配过的左括号
            stack = stack[:len(stack)-1]
        } else {// 以上状况都不存在时则 len(stack)==0 || 没有与右括相匹配的左括号,则该字符串不非法
            return false
        }
    }
    // 最初判断栈内是否还有空余字符,若有阐明有残余的左括号,该字符串也不非法
    return len(stack) == 0
}

func main() {result := isValid("{[}}")
    fmt.Println(result)
}

提交截图

退出移动版