這個問題很簡單，大學(xué)學(xué)數(shù)據(jù)結(jié)構(gòu)的時候，講堆棧一章的時候作為其中一個例子來說的。但是如果面試中被問到這個題，我想用堆棧來做應(yīng)該不能被接受吧，理由是空間和時間的代價都挺高的。
有沒有稍微好點的算法呢？介紹個時間O(n), 空間O(1)的算法。
既然我們只是要找出括號有沒有匹配就行了，那我們用一種方式記下左括號和右括號的次數(shù)不就可以了，例如left_count, right_count。它們的差為0不就好了？只要不為0，肯定就不匹配了，對吧？更進(jìn)一步，為啥非要用2個變量呢，一個就夠了嘛。遇到左括號++，遇到右括號--，最后為0即匹配。
1 bool is_brackets_match(char *const input) {
2 if (input != nullptr) {
3 char *p = input;
4 int count = 0;
5
6 while (*p != '\0') {
7 if (*p == '(')
8 ++count;
9 else if (*p == ')')
10 --count;
11
12 p++;
13 }
14
15 if (count == 0)
16 return true;
17 }
18 return false;
19 }