leetcode講解--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.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
           

Note:

1. S

   will have length in range

   [1, 500]

   .

2. S

   will consist of lowercase letters (

   'a'

   to

   'z'

   ) only.

題目位址

講解

這道題我居然一遍過，以前做題或多或少有些小錯誤。這道題我一上手就發現應該盡量阻止對資料的多次周遊，是以如果能周遊一遍得到一些有用的資訊就好了。我用的解法是，建立一個map存儲每個字母的首尾位置（當然實際操作中我用的是兩個map分别存儲字母第一次出現的位置和最後一次出現的位置）。然後如果這一段之間出現了一個字母，它的尾部位置比框住它的這個字母更大，就更新尾部位置，直到尾部位置無法再擴大為止。

Java代碼

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> result = new ArrayList<>();
        char[] c = S.toCharArray();
        Map<Character, Integer> mapStart = new HashMap<>();
        Map<Character, Integer> mapEnd = new HashMap<>();
        for(int i=0;i<c.length;i++){
            if(mapStart.get(c[i])==null){
                mapStart.put(c[i], i);
                mapEnd.put(c[i], i);
            }else{
                mapEnd.put(c[i], i);
            }
        }
        int beginIndex=0;
        while(beginIndex<c.length){
            int endIndex=mapEnd.get(c[beginIndex]);
            for(int i=beginIndex;i<endIndex;i++){
                if(mapEnd.get(c[i])>endIndex){
                    endIndex = mapEnd.get(c[i]);
                }
            }
            result.add(endIndex-beginIndex+1);
            beginIndex = endIndex+1;
        }
        return result;
    }
}