Partition Labels (M)
題目
A string S of lowercase English 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:
Swill have length in range[1, 500].Swill consist of lowercase English letters ('a'to'z') only.
題意
將給定字串劃分成盡可能多的子串，使得同一個字母只出現在一個子串中，
思路
主要思想是記錄每個字母出現的最后一個位置，得到每個字母的出現區間，對于一個字母的出現區間S，如果其中有字母的結束位置大于S的右端點，那么需要更新右端點，直到右端點對應字母的結束位置就是右端點本身，這樣就找到了一個符合條件的子串，
代碼實作
Java
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
int[] ends = new int[26];
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
ends[c - 'a'] = Math.max(ends[c - 'a'], i);
}
int start = 0, end = 0;
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
end = Math.max(end, ends[c - 'a']);
if (end == i) {
ans.add(end - start + 1);
start = i + 1;
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143966.html
標籤：其他