如何找到一串括号,大括号和方括号的有效性？

Question

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

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

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

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

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

Answer 1

参考Matthieu M.的优秀答案,这是C#中的一个实现,看起来效果很好.

/// <summary>
/// Checks to see if brackets are well formed.
/// Passes "Valid parentheses" challenge on www.codeeval.com,
/// which is a programming challenge site much like www.projecteuler.net.
/// </summary>
/// <param name="input">Input string, consisting of nothing but various types of brackets.</param>
/// <returns>True if brackets are well formed, false if not.</returns>
static bool IsWellFormedBrackets(string input)
{
    string previous = "";
    while (input.Length != previous.Length)
    {
        previous = input;
        input = input
            .Replace("()", String.Empty)
            .Replace("[]", String.Empty)
            .Replace("{}", String.Empty);                
    }
    return (input.Length == 0);
}

从本质上讲,它所做的就是删除一对括号,直到没有任何一个被删除; 如果还有什么东西,那么托架的形状就不好了.

格式良好的括号示例:

()[]
{()[]}

格式错误的括号示例:

([)]
{()[}]

Answer 2

实际上,由于Ritchie和Springsteel,有一个确定性的对数空间算法:http://dx.doi.org/10.1016/S0019-9958 ( 72 ) 90205-7(paywalled,抱歉不在线).由于我们需要日志位来索引字符串,因此这是空间最优的.

如果您愿意接受单侧错误,那么有一种算法使用n polylog(n)时间和polylog(n)空间:http://www.eccc.uni-trier.de/report/2009/119 /

Answer 3

如果输入是只读的,我认为我们不能做O(1)空间.众所周知,任何O(1)空间可判定语言都是规则的(即可写为正则表达式).您拥有的字符串集不是常规语言.

当然,这是关于图灵机.我希望固定字RAM机也是如此.