[[439060]]

劃分字母區(qū)間

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

示例：

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

提示：

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

思路

一想到分割字符串就想到了回溯，但本題其實不用回溯去暴力搜索。

題目要求同一字母最多出現(xiàn)在一個片段中，那么如何把同一個字母的都圈在同一個區(qū)間里呢?

如果沒有接觸過這種題目的話，還挺有難度的。

在遍歷的過程中相當于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現(xiàn)過所有字母，最遠也就到這個邊界了。

可以分為如下兩步：

• 統(tǒng)計每一個字符最后出現(xiàn)的位置
• 從頭遍歷字符，并更新字符的最遠出現(xiàn)下標，如果找到字符最遠出現(xiàn)位置下標和當前下標相等了，則找到了分割點

如圖：

劃分字母區(qū)間

明白原理之后，代碼并不復雜，如下：

class Solution { 
public: 
    vector<int> partitionLabels(string S) { 
        int hash[27] = {0}; // i為字符，hash[i]為字符出現(xiàn)的最后位置 
        for (int i = 0; i < S.size(); i++) { // 統(tǒng)計每一個字符最后出現(xiàn)的位置 
            hash[S[i] - 'a'] = i; 
        } 
        vector<int> result; 
        int left = 0; 
        int right = 0; 
        for (int i = 0; i < S.size(); i++) { 
            right = max(right, hash[S[i] - 'a']); // 找到字符出現(xiàn)的最遠邊界 
            if (i == right) { 
                result.push_back(right - left + 1); 
                left = i + 1; 
            } 
        } 
        return result; 
    } 
}; 

空間復雜度：O(1) 使用的hash數(shù)組是固定大小

總結

這道題目leetcode標記為貪心算法，說實話，我沒有感受到貪心，找不出局部最優(yōu)推出全局最優(yōu)的過程。就是用最遠出現(xiàn)距離模擬了圈字符的行為。

但這道題目的思路是很巧妙的，所以有必要介紹給大家做一做，感受一下。