20.有效的括号(对括号字符串进⾏有效判定)题⽬
给定⼀个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满⾜:
左括号必须⽤相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
⽰例 1:
字符串常量的有效字符输⼊: "()"
输出: true
⽰例 2:
输⼊: "()[]{}"
输出: true
⽰例 3:
输⼊: "(]"
输出: false
⽰例 4:
输⼊: "([)]"
输出: false
⽰例 5:
输⼊: "{[]}"
输出: true
来源:⼒扣(LeetCode)
解答
C语⾔
利⽤栈,依次遍历字符串,当为前括号"(""[""{"时,⼊栈,填⼊对应的后括号。
当遍历到的字符不为前括号,且top == -1,则说明是后括号的同时,前⽅没有对应的前括号,返回false;
否则出栈--top。
遍历完毕后,检查top是否为-1,即可判定字符串是否合规。
// 0 ms 5 MB
bool isValid(char * s){
int len = strlen(s);
char stack[len + 1];
int top = -1;
int i;
for(i = 0; i < len; i++) {
if (s[i] == '(') {
stack[++top] = ')';
}
else if (s[i] == '[') {
stack[++top] = ']';
}
else if (s[i] == '{') {
stack[++top] = '}';
}
else if (top == -1 || s[i] != stack[top]) {
return false;
}
else {
--top;
}
}
if (top == -1) {
return true;
} else {
return false;
}
}
golang
go同理,构建栈结构。
需要注意的是,构建栈结构时,go语⾔使⽤slice切⽚进⾏构建。同时应注意⼊栈出栈的具体操作流程
// 0 ms 2 MB
func isValid(s string) bool {
stack := [] byte {}
for i:= 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, ')')
}else if s[i] == '[' {
stack = append(stack, ']')
}else if s[i] == '{' {
stack = append(stack, '}')
}else if len(stack) == 0 || stack[len(stack)-1] != s[i] {
return false
}else {
stack = stack[0:len(stack)-1]
}
}
if len(stack) == 0 {
return true
}else {
return false
}
}
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论