[求助]一道算法题-多括号匹配

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1700 天前的主题，其中的信息可能已经有所发展或是发生改变。

最近面试遇到一道算法题，多括号匹配。使用栈是一种非常容易想到的解法，但是被问到如何不使用栈怎么解决，我就做不出来了。对于一种括号的情况，使用计数器很容易写出来，但是题目有多种括号，例如：(),[],{}。事后自己尝试的实现了下，没有成功（练的少，智商还一般😭）。

空间复杂的要求 O(1)，时间复杂度不限。不允许使用作弊技巧，例如 replace，修改输入变量等方法。 为了简化实现，我们就只考虑(),[]两种括号好了。

第 1 条附言 · 2020-04-06 12:57:51 +08:00

已经在这里找到了有效的解法，经过修改放到leetcode上是可以通过的，我需要研究下这些实现细节。

int is_corresponding_open(const char *to, const char *from, const char c)
{
    int validity = 0;
    int nesting = 0;

    while (to <= from) {

        if (nesting == 1 && *from == c) {
            validity = 1;
            break;
        }

        if (*from == ')' || *from == '}' || *from == ']') {
            ++nesting;
        } else if (*from == '(' || *from == '{' || *from == '[') {
            --nesting;
        }

        --from;
    }

    return validity;
}

bool isValid(char * str_ptr){
    const char *start = str_ptr;
    int count_paren = 0;
    int count_brace = 0;
    int count_bracket = 0;
    int valid_nesting = 1;

    while (*str_ptr && valid_nesting) {

        switch (*str_ptr) {
        case '(':
            ++count_paren;
            break;

        case '{':
            ++count_brace;
            break;

        case '[':
            ++count_bracket;
            break;

        case ')':
            if (is_corresponding_open(start, str_ptr, '(')) {
                --count_paren;                
            } else {
                valid_nesting = 0;
            }
            break;

        case '}':
            if (is_corresponding_open(start, str_ptr, '{')) {
                --count_brace;                
            } else {
                valid_nesting = 0;
            }
            break;

        case ']':
            if (is_corresponding_open(start, str_ptr, '[')) {
                --count_bracket;                
            } else {
                valid_nesting = 0;
            }
            break;
        }

        ++str_ptr;
    }

    return !(count_paren || count_brace || count_bracket) && valid_nesting;
}

目前尚无回复

括号算法题计数器 Replace