LeetCode刷题（96）～分割平衡字符串【巧妙】

题目描述

在一个「平衡字符串」中，‘L’ 和 ‘R’ 字符的数量是相同的。

给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

返回可以通过分割得到的平衡字符串的最大数量。

示例 1：

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。

  

 

  
1
  
2
  
3
 

示例 2：

输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。

  

 

  
1
  
2
  
3
 

示例 3：

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR".

  

 

  
1
  
2
  
3
 

提示：

• 1 <= s.length <= 1000
• s[i] = ‘L’ 或 ‘R’
• 分割得到的每个字符串都必须是平衡字符串。

解答 By 海轰

提交代码（栈实现）

int balancedStringSplit(string s) { stack<char> a; int count=0; for(int i=0;i<s.length();++i) { if(a.empty()) a.push(s[i]); else if((s[i]=='R'&&a.top()=='L')||(s[i]=='L'&&a.top()=='R')) a.pop(); else a.push(s[i]); if(a.empty()) ++count; } return count; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

解答

Demo（巧妙！！！）

int balancedStringSplit(string s) { int sum=0; int res=0; for(char i:s) { sum+=(i-'O'); if(sum==0) ++res; } return res; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

运行结果

Demo

int balancedStringSplit(string s) { int count=0; int res=0; for(char i:s) { if(i=='R') ++count; if(i=='L') --count; if(count==0)  ++res; } return res; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108220766