这是一个创建于 2210 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近面试遇到一道算法题，多括号匹配。使用栈是一种非常容易想到的解法，但是被问到如何不使用栈怎么解决，我就做不出来了。对于一种括号的情况，使用计数器很容易写出来，但是题目有多种括号，例如：(),[],{}。事后自己尝试的实现了下，没有成功（练的少，智商还一般）。
空间复杂的要求 O(1)，时间复杂度不限。不允许使用作弊技巧，例如 replace，修改输入变量等方法。 为了简化实现，我们就只考虑(),[]两种括号好了。
第 1 条附言 2020 年 4 月 6 日
已经在这里找到了有效的解法，经过修改放到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; } 目前尚无回复
Select Language