python - 删除无效括号

Question

在 O(n) 时间复杂度和 O(1) 空间中使用 Python 删除无效括号。我有一些方法需要 O(n log n) 和 O(n^2) 时间以及 O(n) 空间和时间。但是，我正在寻找一个最短的时间。我尝试在网上搜索但找不到任何解决方法。

例如:

input - {}{}{{}}}}}{{{{{}
output - {}{}{{}}{}

还有其他几种边缘情况。

Answer 1

在给定的例子中，嵌套层次如下:

 { } { } { { } } } } } { { { { { }
 1 0 1 0 1 2 1 0-1-2-3-2-1 0 1 2 1

如果您丢弃负数(即时)，

 { } { } { { } } { { { { { }
 1 0 1 0 1 2 1 0 1 2 3 4 5 4

现在从右边开始重复。

 { } { } { { } } { { { { { }
-2-3-2-3-4-3-2-3-4-3-2-1 0 1

和

 { } { } { { } } { }
 0 1 0 1 0 1 2 1 0 1