首页
编程语言

分类

当前位置: 云海天教程网 > 技术新闻 > 编程语言 >正文

Leetcode No.20 Valid Parentheses有效的括号(c++实现)

更新时间:2021-07-22  作者:佚名   来源: 网络转载

Leetcode No.20 Valid Parentheses有效的括号(c++实现)

1. 题目

1.1 英文题目

Given a string s containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

1.2 中文题目

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

1.3输入输出

输入 输出
s = "()" true
s = "()[]{}" true
s = "(]" false
s = "([)]" false
s = "{[]}" true

1.4 约束条件

  • 1 <= s.length <= 104
  • s consists of parentheses only "()[]{}".

2. 分析

2.1 栈方法

这道题观察规律可知,遍历字符时,只需要看上一位即可,也就是说用栈的方法即可。代码如下:

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> hash_map =
        {
            {"(", ")"},
            {"[", "]"},
            {"{", "}"}
        };//定义一个哈希表,通过哈希表查看括号是否对应上
        string temp(1, s[0]);//模拟栈,该字符串只允许字符后入先出
        for (unsigned int i = 1; i < s.size(); i++)//遍历整个字符串
        {
            if (temp.empty() || hash_map[temp.back()] != s[i])//如果栈为空,或者当前字符与栈顶字符不对应,则将该字符压入栈
                temp.push_back(s[i]);
            else
                temp.pop_back();//如果当前字符与栈顶字符对应,则将栈顶字符弹出
        }
        return temp.empty();
    }
};

2.2 改进算法

我上面的方法相当于是自己构造栈,但是其实c++有现成的栈模板,大神程序如下:

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case "(": 
                case "{": 
                case "[": paren.push(c); break;
                case ")": if (paren.empty() || paren.top()!="(") return false; else paren.pop(); break;
                case "}": if (paren.empty() || paren.top()!="{") return false; else paren.pop(); break;
                case "]": if (paren.empty() || paren.top()!="[") return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};

参考:https://leetcode.com/problems/valid-parentheses/discuss/9252/2ms-C%2B%2B-sloution

作者:云梦士
出处:http://www.cnblogs.com/yunmeng-shi/
本文版权归作者和云海天共有,欢迎转载,但必须给出原文链接,并保留此段声明,否则保留追究法律责任的权利。
上一篇:前端调用接口成功但后端没收到请求 下一篇:别再到处 new 对象了,试试 3 大工厂模式,真香!!
小编推荐
快速导航更多>>
JavaScript 教程 HTML5 教程 CSS3 教程 jQuery 教程 Vue.js 教程 Node.js 教程 SQL 教程 C 教程 PHP 教程 Linux 教程 Docker 教程 Nginx 教程 Python 教程 Java 教程

云海天教程网 版权所有

陕ICP备14013131号-3