首頁>技術>

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準時推送一道經典演算法題目,我選擇的每道題目都不是孤立的,而是由淺入深,環環相扣,幫你梳理演算法知識脈絡,輕鬆學演算法!

14
最新評論
  • BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • REST API設計的9個最佳實踐