題目連結:
題目意譯:
平衡字串為那些有著等量的 'L' 和 'R' 字元的字串。
給定一個平衡字串 s,將其分割為盡可能多的平衡字串。
回傳所能分割出來的平衡字串最大數(shù)量。
限制:
1 ≦ s.length ≦ 1000
s[i] 只會是 'L' 或是 'R'。
s 為平衡字串。
範例測資:
範例 1:
輸入: s = "RLRRLLRLRL"
輸出: 4
解釋: s 可以分割為 "RL" 、 "RRLL" 、 "RL" 、 "RL",每個子字串各自包含著相同數(shù)量的 'L' 和 'R'。
範例 2:
輸入: s = "RLLLLRRRLR"
輸出: 3
解釋: s 可以分割為 "RL" 、 "LLLRRR" 、 "LR",每個子字串各自包含著相同數(shù)量的 'L' 和 'R'。
範例 3:
輸入: s = "LLLLRRRR"
輸出: 1
解釋: s 可以分割為 "LLLLRRRR",每個子字串各自包含著相同數(shù)量的 'L' 和 'R'。
範例 4:
輸入: s = "RLRRRLLRLL"
輸出: 2
解釋: s 可以分割為 "RL" 、 "RRRLLRLL",每個子字串各自包含著相同數(shù)量的 'L' 和 'R'。
解題思維:
有點類似括號匹配的問題(如
這題),但是因為只要求「等量」,所以我們只需掃過 s 並即時記錄 'L' 與 'R' 的數(shù)量。
當 'L' 的數(shù)量 = 'R' 的數(shù)量時,即代表著我們找到了一個切割點,使得當前這個切割點到上一個切割點之間會是等量的 'L' 以及 'R',因此答案數(shù)量 + 1。
掃完之後,上述的答案計量就是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。