763. Partition Labels

Leetcode 問題: 763. Partition Labels
Categories:
Tags:

題目

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

傳入一字串 s，確保字串 s 中的 字母，在後面都不會再出現，那麼前面的 字母區塊 就會形成一個獨立的區塊，找出每個區塊的大小，並回傳所有區塊的大小陣列

Example

e.g. ababcbacadefegdehijhklij

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
字串s a b a b c b a c a d e f e g d e h i j h k l i j
區塊 1 a b a b c b a c a
區塊 2 d e f e g d e
區塊 3 h i j h k l i j
  • 區塊 1 的所有字母不會出現在其他區塊，總共有 9 個字母，所以區塊大小是 9
  • 區塊 2 的所有字母不會出現在其他區塊，總共有 7 個字母，所以區塊大小是 7
  • 區塊 3 的所有字母不會出現在其他區塊，總共有 8 個字母，所以區塊大小是 8

所以 所有區塊的大小陣列 為 [9, 7, 8]

Input: s = "eccbbbbdec"
Output: [10]

演算法

1. 找出所有字母最後出現位置索引對應 Mapping

找出字母最後出現的索引位置，表示可以確保，這個索引之後，就不會再有這個字母出現了，可以拿來當作參考點

2. 檢查最後出現索引位置之前的所有字母

檢查一個字母，需要的切割空間就會增加 1

如果「新的字母」的最後出現索引位置，比「前面字母」索引位置還要「再小」，表示在原本的範圍，就可以將字母匡選出同一個切割區塊

如果「新的字母」的最後出現索引位置，比「前面字母」索引位置還要「再大」，表示在原本的範圍，無法將字母匡選出同一個切割區塊，所以必須要延長切割空間區塊到目前位置

3. 確認切割空間

若 檢查的字母 位置與 切割空間檢查點 位置相同，表示已經檢查完整個要切割的空間了，表示切割空間檢查點前面的所有字母，在後方都不會再出現了，所以可以生成新的區塊

所以可以記錄此 區塊大小，並重設 區塊大小，重新找新的區塊，直到找完所有的子母

答案

JavaScript

/**
 * @param {string} checkText
 * @return {number[]}
 */
var partitionLabels = function(checkText) {
    // 字母最後出現位置索引對應 Mapping
    let LetterLastIndexMapping = new Map();

    // 設定字母最後索引對應
    for (let letterIndex = 0; letterIndex < checkText.length; letterIndex++) {
        // 目前字母
        let currentLetter = checkText[letterIndex];
        // 設定字母最後出現位置對應索引
        // - 因為是要找最後出現，所以後面的字母索引位置可以直接覆蓋之前的位置
        LetterLastIndexMapping.set(currentLetter, letterIndex);
    }

    // 切割字母結果陣列
    let partitionLetterResult = [];
    // 目前切割空間大小
    let partitionSize = 0;
    // 目前切割空間，最後出現字母的索引位置
    let partitionLetterEndIndex = 0;

    // 尋找可以切割的字母空間
    for (let letterIndex = 0; letterIndex < checkText.length; letterIndex++) {
        // 目前字母
        let currentLetter = checkText[letterIndex];
        // 目前字母最後出現索引位置
        let currentLetterLastIndex = LetterLastIndexMapping.get(currentLetter);
        // 切割空間 +1
        partitionSize++;
        // 目前切割空間，最後出現字母的索引位置，確認是否需要把空間再擴大
        // - 如果「新的字母」的最後出現索引位置，比「前面字母」索引位置還要「再小」，表示在原本的範圍，就可以將字母匡選出同一個切割區塊
        // - 如果「新的字母」的最後出現索引位置，比「前面字母」索引位置還要「再大」，表示在原本的範圍，無法將字母匡選出同一個切割區塊，所以必須要延長切割空間區塊到目前位置
        partitionLetterEndIndex = Math.max(partitionLetterEndIndex, currentLetterLastIndex);

        if (letterIndex == partitionLetterEndIndex) {
            // 如果「目前的索引位置」是「切割區塊」的切割點
            // 表示前面的所有字母，在後方都不會再出現了，所以可以生成新的區塊
            // 將前面的區塊大小寫入最後結果
            partitionLetterResult.push(partitionSize);
            // 區塊大小重設，重新尋找新的區塊
            partitionSize = 0;
        }
    }


    return partitionLetterResult;
};

參考資料