Problem 301: Remove Invalid Parentheses
思路
我们 care 的只是括号,其他的元素一概置之不理。
我么用一个 count 来 maintain 括号的数量:如果是
(
我们就加 1;如果是)
我们就减 1。这个过程实际上起的作用就是一个 stack我么可以先处理右括号多的情况:
()))
类型。i
先走,走的每一步都看一下 counter,如果属于这个类型,开始递归。j
这个时候开始走,当它是上一个j
或者第一个右括号的时候,我们把它删掉。这个过程中,我们要记录上一次
i
和j
的位置。如果是左括号多的情况:
((()
类型。我们可以复用原来的代码。
复杂度
The whole search space is a tree with k leaves. The number of nodes in the tree is roughly O(k)
. But this is not always true, for example a degenerated tree.
To generate one node it requires
O(n)
time from the string concatenation among other things. So roughlyO(nk)
. AccuratelyO(nm)
where m is the total "number of recursive calls" or "nodes in the search tree". Then you need to relate m to n in the worst case.
易错点
记得 return
dfs 最重要的就是找到退出的场景
仔细理解最后一段 reverse 的过程
这个是用来 check 是否是 reversed version。如果已经 reverse 过,就不用担心了,说明正反两个顺序都 check 过了。反之接着 check
Last updated