2021-09-18:给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

福大大 答案2021-09-18:

栈。遍历字符串,遇到左括号,入栈;遇到右括号,出栈。如果中途栈的元素个数小于0;或者遍历完成,栈还有元素;或者元素不匹配,就返回false,否则返回true。

代码用golang编写。代码如下:

package main

import "fmt"

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

func isValid(s string) bool {
    if len(s) == 0 {
        return true
    }
    str := []byte(s)
    N := len(str)
    stack := make([]byte, N)
    size := 0
    for i := 0; i < N; i++ {
        cha := str[i]
        if cha == '(' || cha == '[' || cha == '{' {
            stack[size] = twoSelectOne(cha == '(', ')', (twoSelectOne(cha == '[', ']', '}')))
            size++
        } else {
            if size == 0 {
                return false
            }
            size--
            last := stack[size]
            if cha != last {
                return false
            }
        }
    }
    return size == 0
}

func twoSelectOne(c bool, a byte, b byte) byte {
    if c {
        return a
    } else {
        return b
    }
}

执行结果如下:
图片


左神java代码