LeetCode[简单] 20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

思路：

利用stack的性质，遍历string，遇到左半部分，将相应的右半部分放入栈中

遍历时，有三种情况

1. 栈空，string未结束，返回false
2. string[i]与栈顶元素不同，返回false
3. 栈非空，遍历结束，返回false 或者 遍历结束，且栈为空，返回true

public class Solution {
    public bool IsValid(string s) {
        var len = s.Length;
        if(len % 2 != 0)    return false;
        Stack<char> stack = new Stack<char>();
        for(int i = 0; i < len; i++)
        {
            if(s[i] == '(')
                stack.Push(')');
            else if(s[i] == '{')
                stack.Push('}');
            else if(s[i] == '[')
                stack.Push(']');
            else if(stack.Count == 0 || s[i] != stack.Pop())//栈空 或者 栈顶与s[i]不等
                return false;
        }
        if(stack.Count == 0)//遍历结束，栈空
            return true;
        else return false;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。当 n 是奇数时直接返回 false，时间复杂度是 O(1)。当 n 是偶数时，需要遍历字符串 s 一次，每个字符的操作时间都是 O(1)，总时间复杂度是 O(n)。
• 空间复杂度：O(n)，其中 n 是字符串 s 的长度。空间复杂度主要取决于栈空间，栈内的元素个数为 O(n)。

原文地址：https://blog.csdn.net/Theolulu/article/details/142413905

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！