题意
给定一个只包括{}()[]的字符串，判断字符串是否能够成合法的括号序列。
思路
- 直接用栈模拟，时间复杂度(O(n))，但一共就这三种类型，我可以直接三个变量标记就可以了，这样空间复杂度(O(1))。我看错了，原来括号不可以这样嵌套：
([)]，所以只好用栈了（实际上用数组模拟了栈）。
代码
class Solution {
public:
bool isValid(string s) {
char ok[128];
ok[')'] = '(';
ok[']'] = '[';
ok['}'] = '{';
char a[11111];
int len = s.size(), idx = 0;
for(int i = 0; i < len; i)
{
// cout << s[i] << ' ';
if(s[i] == '(' || s[i] == '{' || s[i] == '[')
a[idx ] = s[i];
else
{
if(idx > 0 && ok[s[i]] == a[idx - 1])
--idx;
else
return false;
}
// printf("%c %dn", s[i], idx);
}
// cout << idx << endl;
return idx == 0;
}
};总结
我爱水题。