专栏首页给永远比拿愉快Leetcode: Valid Parentheses

Leetcode: Valid Parentheses

题目: Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

分析: 遍历字符串,使用栈依次存储字符,遇到’0’,’]’,’}’出栈进行判断。 注意:’(‘和’)’只差为1,’[‘和’]’只差为2,’{‘和’}’只差为2,这可以帮助我们判读左括号和右括号是否成对。 C++示例代码:

class Solution
{
public:
    bool isValid(string s)
    {
        string::size_type length = s.length();
        //如果给定的字符个数为奇数,直接返回false
        if (length % 2)
        {
            return false;
        }
        stack<char> chstack;
        char top;//当前栈顶的元素
        //用于记录current和previous元素只差,'('和')'只差为1,'['和']'只差为2,'{'和'}'只差为2
        int distance;
        for (size_t i = 0; i < length; i++)
        {

            if (s[i] == ')' || s[i] == ']' || s[i] == '}')
            {

                if (chstack.empty())
                {
                    return false;
                }
                else
                {
                    top = chstack.top();
                    chstack.pop();
                    distance = s[i] - top;
                    //判断previous和current是否匹配
                    if (distance != 1 && distance != 2)
                    {
                        return false;
                    }
                }
            }
            else
            {
                chstack.push(s[i]);
            }
        }
        //栈为空返回true,否则肯定有不匹配的括号在栈中返回false
        return chstack.empty() ? true : false;
    }
};

C#示例代码:

public class Solution
{
    public bool IsValid(string s)
    {
        if (s.Length % 2 == 1) return false;
        Stack<char> chstack = new Stack<char>();
        char top= ' ';
        int distance = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == ')' || s[i] == ']' || s[i] == '}')
            {
                if (chstack.Count == 0)
                {
                    return false;
                }
                else
                {
                    top= chstack.Pop();
                    distance = s[i] - top;
                    if (distance != 1 && distance != 2)
                    {
                        return false;
                    }
                }
            }
            else
            {
                chstack.Push(s[i]);
            }
        }
        return chstack.Count == 0 ? true : false;
    }
}

Python代码: Python代码我没有使用判读左括号和右括号距离的方法

class Solution:
    # @return a boolean
    def isValid(self, s):
        length = len(s)
        stack = []
        if length % 2 != 0:
            return False
        for i in range(length):
            if s[i] == ')' or s[i] == ']' or s[i] == '}':
                if not stack:
                    return False
                else:
                    top = stack.pop()
                    if top == '(' and s[i] != ')'  or top == '[' and s[i] != ']' or top == '}' and s[i] != '}':
                        return False
            else:
                stack.append(s[i])
        if stack:
            return False
        else:
            return True

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode: Palindrome Number

    题目: Determine whether an integer is a palindrome. Do this without extra space.

    卡尔曼和玻尔兹曼谁曼
  • Leetcode: Set Matrix Zeroes

    题目: Given a m x n matrix, if an element is 0, set its entire row and column to...

    卡尔曼和玻尔兹曼谁曼
  • Leetcode: Search a 2D Matrix

    题目: Write an efficient algorithm that searches for a value in an m x n matrix....

    卡尔曼和玻尔兹曼谁曼
  • 斗地主算法

           不得不承认,算法搁置了一些时间,代码的风格下降了好多!  贴上一个曹点多多且丑的代码!  Orz...  题目要求:      编码:3表示3点 ...

    Gxjun
  • k8s源码-揭开scheduler的算法面纱(下)

    先回顾下优选算法执行的流程,针对每个pod,先使用16个协程并行进行Map操作,Map操作每次要遍历配置的所有的的优选算法,建立node和算法的映射关系,然后并...

    ascehuang
  • 从AFNetworking源码分析到应用全解 原

        AFNetworking是iOS/OS开发中常用的一个第三方网络库,可以说它是目前最流行的网络库,但其代码结构其实并不复杂,也可以说非常简洁优美。在AF...

    珲少
  • LeetCode 468. 验证IP地址

    IPv4 地址由十进制数和点来表示,每个地址包含4个十进制数,其范围为 0 - 255, 用(".")分割。比如,172.16.254.1;

    Michael阿明
  • 使用Source Monitor检测Java代码的环复杂度

    Today I found a useful free software called “SourceMonitor” which can help to ca...

    Jerry Wang
  • 使用Source Monitor检测Java代码的环复杂度

    Today I found a useful free software called “SourceMonitor” which can help to ca...

    Jerry Wang
  • 三种Fibonacci数列第n项计算方法及其优劣分析

    感谢国防科技大学刘万伟老师和中国传媒大学胡凤国两位老师提供的思路,文章作者不能超过8个字符,我的名字就写个姓吧,名字不写了^_^。另外,除了本文讨论的三种方法,...

    Python小屋屋主

扫码关注云+社区

领取腾讯云代金券