LeetCode | 6. Valid Parentheses 有效的括号

Puran

关注

发布于: 2020 年 06 月 28 日

Valid Parentheses 是 LeetCode 算法题库中的第二十道题，难度为 Easy，题目地址为： https://leetcode.com/problems/valid-parentheses/

1. 问题描述

给定一个只包括 (, )，{，}，[，] 的字符串，判断字符串是否有效。有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例：

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

复制代码

2. 解题思路

一开始看到这个题目是一脸茫然，完全不知道如何去下手，在看了官方提供的解题思路后，还是不知道怎么去做。看完提供的 Solution 后，才知道原来还是可以继续用堆栈的概念，而这，我之前是有做过相关的题目的。

本算法题有很多种解题思路，这里列出来两种，1）是用堆栈的方法，2）是匹配相同字符串的方法。

堆栈方法，该方法的思路是有效的括号内部是由各个有效的括号组成的。构造一个包含所有括号的字典，将每个字符拿出来，与栈里的内容进行比较，如果能找到与之匹配的括号，则 Pop 出去，否则继续放在栈中。
匹配字符串方法，该方法比较巧，其思路也是通过内部的有效括号来进行判断。有效的括号内部肯定是这三种括号(), [], {} 的组合，通过字符串的替换方法来将括号依次替换为""来完成判断。

3. 知识点

Python

Python 本身是包含列表和元组这样的顺序表的，因此可以通过列表来完成栈的实现。在 Python 列表中，pop() 函数就是推出列表中的最后一个元素。

这里有一个不懂的地方，这个#号在这里是干啥的呢？

assign a dummy value of '#' to the top_element variable. top_element = stack.pop() if stack else '#'

4. 代码

Python

class Solution:  def isValid(self, s: str) -> bool:    stack = []    # 这里要注意是以闭括号为Key    mapping = {")":"(", "}":"{", "]":"["}
    for char in s:      if char in mapping:        # assign a dummy value of '#' to the top_element variable        top_element = stack.pop() if stack else "#"        if mapping[char] != top_element:          return False        else:          stack.append(char)
          return not stack

复制代码

字符串替换

class Solution:  def isValid(self, s: str) -> bool:    while "()" in s or "{}" in s or "[]" in s:      s = s.replace("()", "").replace("{}", "").replace("[]", "")      return s == ''

复制代码

C#

C#目前只实现了字符串替换方法

public class Solution {    public bool IsValid(string s) {        while (s.Contains("()") || s.Contains("{}") || s.Contains("[]"))        {            s = s.Replace("()", "").Replace("{}", "").Replace("[]", "");        }        return s == "";    }}

复制代码

虽然字符串替换方法比较简单，但是效率很低。

发布于: 2020 年 06 月 28 日阅读数: 70

原文链接:【http://xie.infoq.cn/article/deb5764d5a4c4d01c65d282c7】。文章转载请联系作者。

Puran

关注

GIS从业者，正在往开发的路上小跑。 2018.03.29 加入

从业4年的GIS开发小白，work@esri。

发布

暂无评论

创作场景

LeetCode | 6. Valid Parentheses 有效的括号

1. 问题描述

2. 解题思路

3. 知识点

Python

4. 代码

Python

C#

Puran

评论