题目
结果
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public List<Integer> partitionLabels(String S) {
Map<Character, Integer> map = lastOne(S);
List<Integer> ans = new LinkedList<>();
int left = 0, right = 0, river = 0;
do {
right = Math.max(right, map.get(S.charAt(left)));
if (left == right) {
ans.add(left - river + 1);
river = left + 1;
}
left++;
} while (left != S.length());
return ans;
}
private Map<Character, Integer> lastOne(String s) {
Map<Character, Integer> map = new HashMap<>();
for (int i = s.length() - 1; i >= 0; i--) {
char ch = s.charAt(i);
if (!map.containsKey(ch)) {
map.put(ch, i);
}
}
return map;
}
}
|
复杂度
时间复杂度：O（n），两次遍历String
空间复杂度：O（1），最坏情况下，map中存入26个键值对