763.Partition Labels

原题&翻译

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
给出小写字母组成的字符串 S. 需要给字符串尽可能多的分区, 使得 S 中任意字母在至多一个分区中匹配到, 返回每个部分的分区长度.

Example 1:

注意:

  1. S[1, 500].

  2. S will consist of lowercase letters (‘a’ to ‘z’) only.


解题思路

可以 O(n^2) 暴力, 从头开始遍历, 假设第一个分区 s1 为 S 中第一个字母, 从第二个元素开始遍历剩余长度, 如果剩余字符中的字符在 s1 中出现过, 拓宽 s1 的长度, 直到 S 中剩余字母都不在 s1 中出现, 第一段分区完成, 而后类似

稍好一点, 可以维护一个字母映射 m , 记录每一个字母最后出现的位置, 而后遍历一遍 S, 同时以 m 中的最大长度值作为分区长度, 不断扩大分区至无法扩大, 此时第一个分区维护完毕, 而后类似

via: partition-labels

Hello world!
文章已创建 197

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部