判断字符串是都按正确格式闭合
思路:
当一个字符被看到时, 预料与之对应的字符, 当该字符不是预料的字符, 有两种可能
- 失败
- 被包含, 例如 ({}), 当看到 ‘(‘ 时候, 我们想要的是 ‘)’. 但该语句是合法的
如果是第二种, 那么 ‘(‘ 要被保存起来, 这种数据结构非常适合用栈来做
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
bool isValid(string s) {
if (!s.size()) return true;
if (s.size() < 2) return false;
map<char, char> lettermap{
{'(', ')'},
{'{', '}'},
{'[', ']'},
};
vector<char> vch{ s[0] };
for (int i = 1; i < s.size(); ++i) {
if (lettermap[vch.back()] != s[i]) vch.push_back(s[i]);
else {
vch.pop_back();
if (vch.size()) {}
else if (++i < s.size())
vch.push_back(s[i]);
}
}
return !vch.size();
}
};
|
该代码并未在循环中判断是否合法
实际情况中, 可能一个非常长的字符串一开始就错了, 比如; “){}{}{}{}…”
但是依旧会将整个字符串循环一次, 这样做有三点考虑:
- 代码更加简单, 简洁. 更容易理解
- 如果代码的确需要很多判断才能确定结果, 那么多加条件语句反而是一种额外的消耗
并且是O(n)复杂度, 节省的效率并不会有多少, 同时额外的消耗并不一定会比加条件语句多
- 懒
PS: 如果能想到用栈结构来做这个题的话, 会方便很多. 如果没想到的话, 可能会越想越难.