algorithm - 如何查找一串括号、大括号和方括号的有效性？

Question

我最近接触到这个有趣的问题。给你一个字符串，只包含字符 '(', ')', '{', '}'，'[' and ']'，例如"[{()}]"，需要写一个函数这将检查这样一个输入字符串的有效性，函数可能是这样的:
bool isValid(char* s);
这些括号必须以正确的顺序闭合，例如 "()" 和 "()[]{}" 都是有效的，但 "(]"、"([)]" 和 "{{{{" 不是!

我提出了以下 O(n) 时间复杂度和 O(n) 空间复杂度的解决方案，效果很好:

1. 维护一堆字符。
2. 每当您找到左大括号 '('、'{' 或 '[' 时，将其压入堆栈。
3. 每当您找到右大括号 ')'、'}' 或 ']' 时，检查堆栈顶部是否是相应的左括号, 如果是，则弹出堆栈，否则中断循环并返回 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);
}

本质上，它所做的只是删除成对的括号，直到没有要删除的为止；如果还有任何内容，则括号格式不正确。

格式正确的括号示例:

()[]
{()[]}

畸形括号示例:

([)]
{()[}]