763.劃分字母區間
題目連結:https://leetcode-cn.com/problems/partition-labels/
字串 S 由小寫字母組成。我們要把這個字串劃分為儘可能多的片段,同一字母最多出現在一個片段中。返回一個表示每個字串片段的長度的列表。
示例:輸入:S = "ababcbacadefegdehijhklij"輸出:[9,7,8]解釋:劃分結果為 "ababcbaca", "defegde", "hijhklij"。每個字母最多出現在一個片段中。像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的,因為劃分的片段數較少。
提示:
S的長度在[1, 500]之間。S只包含小寫字母 'a' 到 'z' 。思路一想到分割字串就想到了回溯,但本題其實不用回溯去暴力搜尋。
題目要求同一字母最多出現在一個片段中,那麼如何把同一個字母的都圈在同一個區間裡呢?
如果沒有接觸過這種題目的話,還挺有難度的。
在遍歷的過程中相當於是要找每一個字母的邊界,「如果找到之前遍歷過的所有字母的最遠邊界,說明這個邊界就是分割點了」。此時前面出現過所有字母,最遠也就到這個邊界了。
可以分為如下兩步:
統計每一個字元最後出現的位置從頭遍歷字元,並更新字元的最遠出現下標,如果找到字元最遠出現位置下標和當前下標相等了,則找到了分割點如圖:
763.劃分字母區間
明白原理之後,程式碼並不複雜,如下:
class Solution {public: vector<int> partitionLabels(string S) { int hash[27] = {0}; // i為字元,hash[i]為字元出現的最後位置 for (int i = 0; i < S.size(); i++) { // 統計每一個字元最後出現的位置 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']); // 找到字元出現的最遠邊界 if (i == right) { result.push_back(right - left + 1); left = i + 1; } } return result; }};
時間複雜度:O(n)空間複雜度:O(1),使用的hash陣列是固定大小總結這道題目leetcode標記為貪心演算法,說實話,我沒有感受到貪心,找不出區域性最優推出全域性最優的過程。就是用最遠出現距離模擬了圈字元的行為。
但這道題目的思路是很巧妙的,所以有必要介紹給大家做一做,感受一下。
打算從頭開始打卡的錄友,可以在「演算法彙總」這裡找到歷史文章,很多錄友都在從頭打卡,你並不孤單!
我是程式設計師Carl,個人主頁:https://github.com/youngyangyang04
這裡每天8:35準時推送一道經典演算法題目,我選擇的每道題目都不是孤立的,而是由淺入深,環環相扣,幫你梳理演算法知識脈絡,輕鬆學演算法!