相关疑难解决方法(0)

我最近接触到了这个有趣的问题.您将获得只包含字符的字符串'(',')','{','}','['和']',例如"[{()}]",你需要写这将检查这些输入字符串的有效性的函数,函数可能是这样的:
bool isValid(char* s);
这些支架必须关闭以正确的顺序,例如"()"和"()[]{}"都是有效的,但是"(]","([)]"并且"{{{{"都没有!

我推出了以下O(n)时间和O(n)空间复杂度解决方案,它工作正常:

1. 保持一堆字符.
2. 无论何时找到开口支撑'(','{'或'['将其推到堆叠上.
3. 每当你找到关闭括号时')','}'OR ']',检查堆栈顶部是否是相应的开括号,如果是,则弹出堆栈,否则打破循环并返回false.
4. 重复步骤2 - 3直到字符串结束.

这是有效的,但我们可以优化空间,可以是恒定的额外空间,我知道时间复杂度不能小于O(n),因为我们必须看每个角色.

所以我的问题是我们可以在O(1)空间中解决这个问题吗？

在我的Python应用程序中,我需要编写一个匹配C++ for或while循环的正则表达式,该循环使用分号(;).例如,它应匹配此:

for (int i = 0; i < 10; i++);

......但不是这个:

for (int i = 0; i < 10; i++)

这看起来很琐事,直到您意识到开括号和右括号之间的文本可能包含其他括号,例如:

for (int i = funcA(); i < funcB(); i++);

我正在使用python.re模块.现在我的正则表达式看起来像这样(我已经留下了我的评论,所以你可以更容易理解):

# match any line that begins with a "for" or "while" statement:
^\s*(for|while)\s*
\(  # match the initial opening parenthesis
    # Now make a named group 'balanced' which matches a balanced substring.
    (?P<balanced>
        # A balanced substring is either something that is not …