题目
题目描述
在一个 平衡字符串 中,‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。
注意:分割得到的每个字符串都必须是平衡字符串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例 1:
输入:s = “RLRRLLRLRL”
输出:4
解释:s 可以分割为 “RL”、“RRLL”、“RL”、“RL” ,每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
示例 2:
输入:s = “RLLLLRRRLR”
输出:3
解释:s 可以分割为 “RL”、“LLLRRR”、“LR” ,每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
示例 3:
输入:s = “LLLLRRRR”
输出:1
解释:s 只能保持原样 “LLLLRRRR”.
示例 4:
输入:s = “RLRRRLLRLL”
输出:2
解释:s 可以分割为 “RL”、“RRRLLRLL” ,每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
提示:
- 1 <= s.length <= 1000
- s[i] = ‘L’ 或 ‘R’
- s 是一个 平衡 字符串
来源
来源:力扣(LeetCode)
链接:https:///problems/split-a-string-in-balanced-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
解法1
class Solution {
/**
* <p>思路:栈。如果栈为空则入栈,如果栈不为空则与栈顶元素比较,如果相同则入栈,如果不同则将栈顶元素出栈,如果出栈后栈空则表示存在一个平衡子字符串。即用'L'抵消'R'。</p>
* <p>结果:成功</p>
* <ul>
* <li>执行用时:2 ms, 在所有 Java 提交中击败了9.18% 的用户</li>
* <li>内存消耗:36 MB, 在所有 Java 提交中击败了83.26% 的用户</li>
* <li>通过测试用例:40 / 40</li>
* </ul>
*
* @param s 平衡字符串
* @return 可以通过分割得到的平衡字符串的最大数量
*/
public int balancedStringSplit(String s) {
// 平衡子字符串的个数
int count = 0;
// 栈
Stack stack = new Stack();
char[] chars = s.toCharArray();
// 循环遍历每个字符
for (char aChar : chars) {
// 如果栈为空则将字符入栈
if (stack.isEmpty()) {
stack.push(aChar);
} else {
// 如果栈不为空则将元素出栈比较
char top = (char) stack.peek();// 获取栈顶元素
// 如果栈顶元素与当前字符相同,则继续入栈
if (top == aChar) {
stack.push(aChar);
} else {
// 如果不相同则出栈
stack.pop();
// 如果栈空则表示完成了一个平衡子字符串的分割,则计数器加一
if (stack.isEmpty()) {
count++;
}
}
}
}
return count;
}
}
解法1代码的简化:
public class Solution {
/**
* <p>思路:解法1的优化。</p>
* <p>结果:成功</p>
* <ul>
* <li>执行用时:1 ms, 在所有 Java 提交中击败了34.28% 的用户</li>
* <li>内存消耗:36.3 MB, 在所有 Java 提交中击败了33.33% 的用户</li>
* <li>通过测试用例:40 / 40</li>
* </ul>
*
* @param s 平衡字符串
* @return 可以通过分割得到的平衡字符串的最大数量
*/
public int balancedStringSplit(String s) {
int count = 0;
Stack stack = new Stack();
char[] chars = s.toCharArray();
for (char aChar : chars) {
// 优化了解法1种的if-else判断
if (stack.isEmpty() || (char) stack.peek() == aChar) {
stack.push(aChar);
} else {
stack.pop();
count += stack.isEmpty() ? 1 : 0;
}
}
return count;
}
}
解法2
public class Solution {
/**
* <p>思路:贪心。为了最大化分割数量,我们可以不断循环,每次从s中分割出一个最短的平衡前缀,由于剩余部分也是平衡字符串,我们可以将其当作s继续分割,直至s为空时,结束循环。</p>
* <p>结果:成功</p>
* <ul>
* <li>执行用时:0 ms, 在所有 Java 提交中击败了100.00% 的用户</li>
* <li>内存消耗:36.3 MB, 在所有 Java 提交中击败了39.94% 的用户</li>
* <li>通过测试用例:40 / 40</li>
* </ul>
*
* @param s 平衡字符串
* @return 可以通过分割得到的平衡字符串的最大数量
*/
public int balancedStringSplit(String s) {
int count = 0;// 平衡字符串的个数
int balance = 0;// 平衡因子,如果遍历的字符是'R'则加1,如果是'L'则减1,当为0时,表示已经分割得到一个平衡字符串
char[] chars = s.toCharArray();
for (char aChar : chars) {
if (aChar == 'R') {
balance++;
} else {
balance--;
}
count += balance == 0 ? 1 : 0;
}
return count;
}
}