[[422180]]

本文轉載自微信公眾號「程序員小熊」，作者Dine 。轉載本文請聯系程序員小熊公眾號。

前言

大家好，我是來自于華為的程序員小熊。今天給大家帶來一道字符串相關的題目，這道題也是今天的力扣每日一題，同時也是華為、蘋果、谷歌和雅虎等大廠的面試題，即力扣上的第1221題-分割平衡字符串。

本文主要介紹貪心+棧的策略來解答此題，供大家參考，希望對大家有所幫助。

分割平衡字符串

在一個平衡字符串中，'L' 和 'R' 字符的數量是相同的。

給你一個平衡字符串 s，請你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個字符串都必須是平衡字符串。

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

示例

示例及提示

解題思路

要求分割得到平衡字符串的最大數量，很容易想到暴力法，只要遍歷一遍字符串，統計字符 'L' 和 'R' 的數量，即可計算出題目要求的結果。

方法一：暴力法

遍歷字符串，統計 'L' 和 'R' 的數量，當其數量相同時，則表明可以當前遍歷到的字符可跟之前的遍歷的那些字符構成平衡字符串，此時統計平衡字符串的個數，并將 'L' 和 'R' 的數量全部置 0，然后繼續遍歷并統計平衡字符串的個數，直至遍歷完整個字符串即可。

Show me the Code

「C」

int balancedStringSplit(char * s) { 
    int numR = 0, numL = 0, res = 0; 
    for (int i = 0; s[i] != '\0'; ++i) { 
        if (s[i] == 'L') { 
            numL++; 
        } else { 
            numR++; 
        } 
 
        if (numL == numR) { 
            res++; 
            numL = 0; 
            numR = 0; 
        } 
    } 
 
    return res;  
} 

復雜度分析

時間復雜度：O(n)，其中 n 為字符串的長度，需要遍歷一遍字符串。

空間復雜度：O(1)，未開辟額外的存儲空間。

方法二：貪心 + 棧

本題也可以采用貪心的思想，遍歷字符串時，遇到一個個平衡字符串時，將其分割出來，再繼續遍歷剩余的子字符串。

同時可以采用棧的思想，在遍歷字符串時，如果遇到字符 'R' 時，讓其入棧，棧內的字符個數加一;遇到字符 'L' 時，讓字符 'R' 出棧，棧內的字符個數減一。

遍歷的同時判斷棧中的字符個數是否為 0，若為 0，則代表已遍歷的字符已構成平衡字符串，統計平衡字符串的個數，直至遍歷結束。

舉例

以字符串 s = "RLLLRRLR" 為例。

例子

在遍歷到 s 的某一字符時，用兩個變量 cnt 和 res 分別記錄字符 'R' 和 'L' 之差以及平衡字符串的數量;

設置兩個變量，邊遍歷邊統計平衡字符串個數

計算 cnt 和 res 的大小;

遍歷到 'R' 時，cnt 加 1

遍歷到 'L'時，cnt 減 1 并計算 res

完整的計算過程，如下動圖示：

計算平衡字符串的完整過程動圖

Show me the Code

「C」

int balancedStringSplit(char * s) { 
    int cnt = 0, res = 0; 
    for (int i = 0; s[i] != '\0'; ++i) { 
        cnt += s[i] == 'R' ? 1 : -1; 
        if (cnt == 0) { 
            res++; 
        } 
    } 
 
    return res;  
} 

「C++」

int balancedStringSplit(string s) { 
    int res = 0, cnt = 0; 
    for (auto a : s) { 
        cnt += a == 'R' ? 1 : -1; 
        if (cnt == 0) { 
            res += 1; 
        } 
    } 
 
    return res; 
} 

「Java」

int balancedStringSplit(String s) { 
    int res = 0, cnt = 0; 
    for (int i = 0; i < s.length(); i++) { 
        cnt += s.charAt(i) == 'R' ? 1 : -1; 
        if (cnt == 0) { 
            res += 1; 
        } 
    } 
 
    return res; 
} 

「Python3」

def balancedStringSplit(self, s: str) -> int: 
    res, cnt = 0, 0         
    for c in s: 
        cnt += 1 if c == 'R' else -1           
        if cnt == 0: 
            res += 1 
         
    return res 

「Golang」

func balancedStringSplit(s string) int { 
    cnt, res := 0, 0 
    for _, ch := range s { 
        if ch == 'R' { 
            cnt++ 
        } else { 
            cnt-- 
        } 
 
        if cnt == 0 { 
            res++ 
        } 
    } 
 
    return res 
} 

復雜度分析

• 時間復雜度：O(n)，其中 n 為字符串的長度，需要遍歷一遍字符串。
• 空間復雜度：O(1)，未開辟額外的存儲空間。