劃分字母區(qū)間

題目

字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一個字母只會出現(xiàn)在其中的一個片段。返回一個表示每個字符串片段的長度的列表。

示例 1：

輸入：S = "ababcbacadefegdehijhklij" 輸出：[9,7,8] 解釋： 劃分結(jié)果為 "ababcbaca", "defegde", "hijhklij"。 每個字母最多出現(xiàn)在一個片段中。 像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數(shù)較少。

提示：

S的長度在[1, 500]之間。 S只包含小寫字母 'a' 到 'z' 。

解題

思路 策略就是不斷地選擇從最左邊起最小的區(qū)間。可以從第一個字母開始分析，假設(shè)第一個字母是 'a'，那么第一個區(qū)間一定包含最后一次出現(xiàn)的 'a'。但第一個出現(xiàn)的 'a' 和最后一個出現(xiàn)的 'a' 之間可能還有其他字母，這些字母會讓區(qū)間變大。舉個例子，在 "abccaddbeffe" 字符串中，第一個最小的區(qū)間是 "abccaddb"。 通過以上的分析，我們可以得出一個算法：對于遇到的每一個字母，去找這個字母最后一次出現(xiàn)的位置，用來更新當(dāng)前的最小區(qū)間。 算法 定義數(shù)組 last[char] 來表示字符 char 最后一次出現(xiàn)的下標(biāo)。定義 anchor 和 j 來表示當(dāng)前區(qū)間的首尾。如果遇到的字符最后一次出現(xiàn)的位置下標(biāo)大于 j， 就讓 j=last[c] 來拓展當(dāng)前的區(qū)間。當(dāng)遍歷到了當(dāng)前區(qū)間的末尾時(即 i==j )，把當(dāng)前區(qū)間加入答案，同時將 start 設(shè)為 i+1 去找下一個區(qū)間。

Python

class Solution {
    public List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        for (int i = 0; i < S.length(); ++i)
            last[S.charAt(i) - 'a'] = i;

        
        int j = 0, anchor = 0;
        List<Integer> ans = new ArrayList();
        for (int i = 0; i < S.length(); ++i) {
            j = Math.max(j, last[S.charAt(i) - 'a']);
            if (i == j) {
                ans.add(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return ans;
    }
}

Java

class Solution(object):
    def partitionLabels(self, S):
        last = {c: i for i, c in enumerate(S)}
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            j = max(j, last[c])
            if i == j:
                ans.append(i - anchor + 1)
                anchor = i + 1

            
        return ans