题目描述

Partition Labels

给定一个全英文小字母组成的的字符串s，尽可能的把该字符串划分为多个部分，每个部分中的每个字母只在当前部分出现。
结果返回一个整数列表，每个数字代表划分后每个部分的字符串长度。

字符串长度为 [1, 500]
所有的输入字符串组成都是 a-z 的小写字符

示例1：

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
划分结果为 "ababcbaca", "defegde", "hijhklij".

划分为 "ababcbacadefegde", "hijhklij" 也是符合要求的，但它不算划分成最多部分的答案

javascript:

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    
};

From leetcode No.763 Medium (opens new window)

解法

点击查看

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(S) {
	if(S.length === 0){
		return [0]
	}
    const map = {};
    for(let i=0; i<S.length; i++){
    	map[S[i]] = i;
    }
    let start = 0
    let end = 0
    const ret = []
    for(let i=0; i<S.length; i++){
    	end = Math.max(end, map[S[i]]);
    	if(i === end || end === S.length - 1){
    		ret.push(end - start + 1)
    		start = end + 1;
    		end = start;
    	}
    }
    return ret
};

总结

• 记录元素的索引使用哈希表
• 区间问题，使用双指针逻辑更清晰
• 一开始想复杂了，认为在字符串中间存在一个独一无二的元素也是一个临界点， 实则是和在字符串起始的情况一样，只是特殊情况，仍包含在规则中。