carloscn
commented
1 year ago 问题分析
使用栈结构。字符入栈操作然后判断：
- 如果是空的，那么直接就push当前的元素
- 如果是非空的：
- 栈中的值和push的值是不相同的，那么当前元素出栈，接着判断一下栈是否为空，如果是空就计数，非空就标记pop过
- 栈中的值和push的值是相同的：
- 检查是否pop过，是，则直接count + 1退出
- 否，直接push当前的元素
pub fn balanced_string_split(s: String) -> i32
{
let mut ret:i32 = 0;
if s.len() < 1 {
return ret;
}
let mut s_stack:Vec<char> = vec![];
let s_chars:Vec<char> = s.chars().collect();
let mut is_poped:bool = false;
for e in s_chars {
if s_stack.is_empty() {
s_stack.push(e);
} else {
if e != s_stack[s_stack.len() - 1] {
s_stack.pop();
if s_stack.is_empty() {
ret += 1;
is_poped = false;
} else {
is_poped = true;
}
} else {
if is_poped {
return ret + 1;
} else {
s_stack.push(e);
}
}
}
}
return ret;
}
问题描述
平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
每个子字符串都是平衡字符串。 返回可以通过分割得到的平衡字符串的 最大数量 。
示例 1：
输入：s = "RLRRLLRLRL" 输出：4 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
示例 2：
输入：s = "RLRRRLLRLL" 输出：2 解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。 注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。 示例 3：
输入：s = "LLLLRRRR" 输出：1 解释：s 只能保持原样 "LLLLRRRR" 。
提示：
2 <= s.length <= 1000 s[i] = 'L' 或 'R' s 是一个 平衡 字符串
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/split-a-string-in-balanced-strings