前往
大廳
主題

LeetCode - 1221. Split a String in Balanced Strings 解題心得

Not In My Back Yard | 2021-04-07 00:00:09 | 巴幣 2 | 人氣 250

題目連結:


題目意譯:
平衡字串為那些有著等量的 'L' 和 'R' 字元的字串。

給定一個平衡字串 s,將其分割為盡可能多的平衡字串。

回傳所能分割出來的平衡字串最大數量。

限制:
1 ≦ s.length ≦ 1000
s[i] 只會是 '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",每個子字串各自包含著相同數量的 'L' 和 'R'。

範例 4:
輸入: s = "RLRRRLLRLL"
輸出: 2
解釋: s 可以分割為 "RL" 、 "RRRLLRLL",每個子字串各自包含著相同數量的 'L' 和 'R'。


解題思維:
有點類似括號匹配的問題(如這題),但是因為只要求「等量」,所以我們只需掃過 s 並即時記錄 'L' 與 'R' 的數量。

當 'L' 的數量 = 'R' 的數量時,即代表著我們找到了一個切割點,使得當前這個切割點到上一個切割點之間會是等量的 'L' 以及 'R',因此答案數量 + 1。

掃完之後,上述的答案計量就是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作