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 } }
执行结果如下: