[[439060]]

劃分字母區(qū)間

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

示例：

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

提示：

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

思路

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

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

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

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

可以分為如下兩步：

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

如圖：

劃分字母區(qū)間

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

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)計(jì)每一個(gè)字符最后出現(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)的最遠(yuǎn)邊界 
            if (i == right) { 
                result.push_back(right - left + 1); 
                left = i + 1; 
            } 
        } 
        return result; 
    } 
}; 

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

總結(jié)

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

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