解題區►Leetcode►Medium

Leetcode 763 - Partition Labels

題目

Problem#

給定一個字串，問你如果把字串分組，靠得近的分在同一組，組數越少越好，要你回傳分組狀態

1
2
3
4
ababcbacadefegdehijhklij => [9, 7, 8]

ababcbaca | defegde | hijhklij
^abc        ^defg     ^hijkl

想法#

如何找組的結尾?看每個字母最後出現的位置(last)，假如第 i 個字母的最後出現就是自己時(即 i == last[i])，則代表碰到了該組的結尾。
先建好字母對最後出現 index 的表，接著掃一遍，碰到結尾紀錄組大小，更新左界右界即可。

  • 時間複雜度: $\mathcal{O}(n)$
  • 空間複雜度: $\mathcal{O}(1)$

AC Code#

賞析#