当前位置：网站首页>2022.04.23 (lc_763_divided into letter interval)

2022.04.23 (lc_763_divided into letter interval)

2022-04-23 18:53:00 【Leeli9316】

Method ： greedy 

class Solution {
    public List<Integer> partitionLabels(String s) {
        // Record the last position of each letter 
        int[] lastPos = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastPos[s.charAt(i) - 'a'] = i;
        }
        List<Integer> ans = new ArrayList<>();
        int start = 0; // Starting position 
        int end = 0; // End position 
        for (int i = 0; i < s.length(); i++) {
            // Update the farthest position where the character appears 
            end = Math.max(end, lastPos[s.charAt(i) - 'a']);
            if (i == end) {
                ans.add(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
}

版权声明
本文为[Leeli9316]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204231851339617.html

边栏推荐

猜你喜欢

随机推荐