一个字符（微博和Twitter的140个字上限意义完全不一样）

2022-10-13：给定一个只包含三种字符的字符串：( 、) 和 *，

写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。

任何右括号 ) 必须有相应的左括号 ( 。

左括号 ( 必须在对应的右括号之前 )。

* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符。

一个空字符串也被视为有效字符串。

输入: "(*))"。

输出: True。

来自蔚来汽车。

答案2022-10-13：

贪心方法。

时间复杂度O(N)。

额外空间复杂度O(1)。

代码用rust编写。代码如下：

impl Solution { pub fn check_valid_string(s: String) -> bool { let str = s.into_bytes(); let mut max = 0; let mut min = 0; for x in str.iter() { if *x == '(' as u8 { max += 1; min += 1; } else { // ) * if *x == ')' as u8 && max == 0 { // 不够减了! return false; } // max 够减 // ) * // max -1 +1 max += if *x == ')' as u8 { -1 } else { 1 }; // min ( - ) 弹性范围中，最小的差值 // ) * min -1 // min == 0 if min > 0 { min -= 1; } } } // 0 ~ 7 // 3 ~ 9 return min == 0; } } fn main() { let s = String::from("(*))"); let ans = Solution::check_valid_string(s); println!("ans = {:?}", ans); } struct Solution {}

执行结果如下：

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_07_3_week/Code02_ValidParenthesisString.java)