leetCode-763划分字母区间

划分字母区间 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。 示例 1： 输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。 提示： S的长度在[1, 500]之间。 S只包含小写字母 ‘a’ 到 ‘z’ 。 注意寻找lastIndexOf（char c）锁定边界 class Solution { public List<Integer> partitionLabels(String S) { List<Integer> res=new ArrayList<>(); int pre=0; for(int i=0;i<S.length();i++){ pre=i; int end=S.lastIndexOf(S.charAt(i)); i=fun(S,i,end); res.add(i-pre+1); } return res; } public int fun(String s,int start,int end){ if(start==end)return start; int bround=-1; for(;start<=end;start++){ end=Math.max(end,s.lastIndexOf(s.charAt(start))); } return end; } }

官方在细节处理的更好，一次遍历存储了lastIndex

class Solution { public List<Integer> partitionLabels(String S) { int[] last = new int[26]; int length = S.length(); for (int i = 0; i < length; i++) { last[S.charAt(i) - 'a'] = i; } List<Integer> partition = new ArrayList<Integer>(); int start = 0, end = 0; for (int i = 0; i < length; i++) { end = Math.max(end, last[S.charAt(i) - 'a']); if (i == end) { partition.add(end - start + 1); start = end + 1; } } return partition; } } 作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/partition-labels/solution/hua-fen-zi-mu-qu-jian-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。