LeetCode | 6. Valid Parentheses 有效的括号

发布于: 2020 年 06 月 28 日
LeetCode | 6. Valid Parentheses 有效的括号

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

1. 问题描述

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

  • 左括号必须用相同类型的右括号闭合。

  • 左括号必须以正确的顺序闭合。

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

示例:

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

2. 解题思路

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

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

  1. 堆栈方法,该方法的思路是有效的括号内部是由各个有效的括号组成的。构造一个包含所有括号的字典,将每个字符拿出来,与栈里的内容进行比较,如果能找到与之匹配的括号,则Pop出去,否则继续放在栈中。

  2. 匹配字符串方法,该方法比较巧,其思路也是通过内部的有效括号来进行判断。有效的括号内部肯定是这三种括号(), [], {} 的组合,通过字符串的替换方法来将括号依次替换为""来完成判断。

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 日 阅读数: 5
用户头像

Puran

关注

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

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

评论

发布
暂无评论
LeetCode | 6. Valid Parentheses 有效的括号