// 模拟，打分; 记录打分区间
// 时间O(n), 空间O(1)
const checkValidString = (s: string): boolean => {
let l: number = 0, r: number = 0;
for (const ch of s) {
if (ch === '(') {
++l, ++r;
} else if (ch === ')') {
--l, --r;
} else if (ch === '*') {
--l, ++r;
}
// 缺失左括号后字符串已经失效
l = Math.max(l, 0);
// 右括号过多
if (l > r) return false;
}
// l > 0 无效
return l === 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20