主題

LeetCode - 830. Positions of Large Groups 解題心得

Not In My Back Yard | 2021-01-22 09:00:04

題目連結:


題目意譯:
小寫字母字串 s 中,這些字母形成好幾個連續相同字母之群組。

例如,字串如 s = "abbxxxxzyy" 有 "a" 、 "bb" 、 "xxxx" 、 "z" 以及 "yy" 這些群組。

一個群組以一個區間 [start, end] 表示,其中 start 以及 end 代表著群組開頭和結尾之索引值(含左右端點)。接續上例,"xxxx" 為區間 [3, 6]。

一個群組若含有三個以上(含)的字母,即會被認為是「大」的。

回傳所有大群組之區間,其中所有區間按照 start 索引值之大小遞增之排序。

限制:
1 ≦ s.length ≦ 1000
s 只包含小寫英文字母。



範例測資:
範例 1:
輸入: s = "abbxxxxzzy"
輸出: [[3,6]]
解釋: "xxxx" 為唯一大群組,其 start 索引值為 3 、end 索引值為 6 。

範例 2:
輸入: s = "abc"
輸出: []
解釋: 我們有群組 "a" 、 "b" 以及 "c",但沒有一個是大群組。

範例 3:
輸入: s = "abcdddeeeeaabbbcd"
輸出: [[3,5],[6,9],[12,14]]
解釋: 大群組為 "ddd" 、 "eeee" 和 "bbb"。

範例 4:
輸入: s = "aba"
輸出: []


解題思維:
參見這題如何統計連續相同字元區段之長度。而既然你可以統計長度,也知道其區段結束於何處(即 end 索引值),則便可以推出其開頭(start 索引值)。

接著判斷每個連續區段,其 end - start 是否 ≧ 3。如果是,則直接將當前的 [start, end] 加入答案之中。

可以注意到,不需要特別排序。因為我們是從左掃到右(索引值小到大),因此答案中每個區間即照著 start 索引值由小到大排。




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

創作回應

更多創作