763. 划分字母区间

package com.wsq.leetcode; /** * 763. 划分字母区间 * @author wsq * @date 2020/10/22 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1： 输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。 链接：https://leetcode-cn.com/problems/partition-labels */ import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class PartitionLabels { /** * 本题解决问题的思路是（后期可以遍历字符串S后去26个字母对应的最后位置，以后看到26个字母要想到使用长度26的数组去记数）： * 1.找到子序列中字符在字符串S中的最后的位置 * 2.遍历子序列开始位置到 暂时的 最后位置中的每一个字符 * 3.在遍历字符的过程中，不断的更新最大的 最后位置 * 4.记录最后位置到起始位置的字符数 * @param S * @return */ public List<Integer> partitionLabels(String S) { int n = S.length(); int startPos = 0; int endPos = 0; int i = 0; List<Integer> ans = new ArrayList(); Set<Character> tmpSet = new HashSet(); while(i < n){ char c = S.charAt(i); endPos = S.lastIndexOf(c, n-1); if(endPos == -1){ ans.add(1); i++; continue; } int j = i + 1; tmpSet.clear(); tmpSet.add(c); while(j < endPos){ c = S.charAt(j); if(tmpSet.contains(c)){ j++; continue; } int tmpEnd = S.lastIndexOf(c, n-1); if(tmpEnd == -1){ continue; } endPos = endPos < tmpEnd ? tmpEnd : endPos; tmpSet.add(c); j++; } ans.add(endPos - startPos + 1); i = endPos + 1; startPos = i; } return ans; } public static void main(String[] args) { String s = "abcdefg"; PartitionLabels pl = new PartitionLabels(); List<Integer> ans = pl.partitionLabels(s); for(int i: ans) { System.out.println(i); } } }