| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (39.23%) | 553 | - |
Tags
string
Companies
Unknown
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号
( 必须有相应的右括号 )。 - 任何右括号
) 必须有相应的左括号 ( 。 - 左括号
( 必须在对应的右括号之前 )。 * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。- 一个空字符串也被视为有效字符串。
示例 1:
示例 2:
示例 3:
注意:
- 字符串大小将在 [1，100] 范围内。
Discussion | Solution
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - 贪心法
pub fn check_valid_string(s: String) -> bool {
let mut unpaired_lefts = 0; //未匹配的'('数
let mut can_pair_rights = 0; //可匹配')'的容量
for c in s.chars() {
match c {
'(' => {
can_pair_rights += 1; // 可匹配')'的容量+1
unpaired_lefts += 1; // 未匹配的'('总数+1
}
')' => {
// 如果没有匹配')'的容量
if can_pair_rights <= 0 {
return false;
}
can_pair_rights -= 1;
// 如果存在未匹配的'('
if unpaired_lefts > 0 {
unpaired_lefts -= 1; //未匹配的'('数量-1
}
}
'*' => {
can_pair_rights += 1; // 可匹配')'的容量+1
// 如果有未匹配的'('
if unpaired_lefts > 0 {
unpaired_lefts -= 1; // 未匹配的'('数-1
};
}
_ => {}
}
}
unpaired_lefts == 0
}
}
// @lc code=end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::check_valid_string("()".into()), true);
assert_eq!(Solution::check_valid_string("(*)".into()), true);
assert_eq!(Solution::check_valid_string("())".into()), false);
assert_eq!(Solution::check_valid_string("*)".into()), true);
assert_eq!(Solution::check_valid_string("(*".into()), true);
assert_eq!(Solution::check_valid_string("(*))".into()), true);
}
}
|