2019-12-17  41 views 评论

Leetcode题目解析(191217):20&22&32

 标签:

Leetcode 20:有效的括号

题目描述

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

有效字符串需满足:

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

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

代码实现

复杂度

时间复杂度:O(n),n为字符串长度
空间复杂度:O(n),n为字符串长度

复杂度分析

Leetcode 22:括号生成

题目描述

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。例如,给出 n = 3,生成结果为:

解题思路

用回溯法可以比较容易的做出来,因为前面回溯法说的比较多了,这里就不再累述。但是有一点注意的是,backtrack()中第三个判断一定要是right<left才可以,而不是right<n,因为right的数量目标是等于left,在已经有了left个左括号的时候,右括号数量right不能超过left。

代码实现

复杂度

复杂度分析

Leetcode 32:最长有效括号

题目说明

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

解题思路

参考:https://leetcode-cn.com/problems/longest-valid-parentheses/solution/c-liang-ci-bian-li-jie-fa-by-da-li-wang/

代码实现

复杂度

复杂度分析
空间复杂度:O(n)【dp数组长度】
时间复杂度:O(n)

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: