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;
};

参考资料