原题地址
思考过程:
从最左字符开始,找到该字符在串中的最右位置,然后从左到右遍历字符,依次找到不同字符的最右位置,如果比上一次记录的最右大,更新最右,直到遍历完成后,左到右表示的字符串,即为一个片段,然后把更新最左,一直到遍历完整个串。
代码实现
public List<Integer> partitionLabels(String s) {
List<Integer> ans = new ArrayList<>();
int lastP = 0;
int p = 1;
Set<Character> set = new HashSet<>();
while (p <= s.length()) {
for (int i = lastP; i < p; i++) {
char c = s.charAt(i);
if (!set.contains(c)) {
int rightPosition = getRightPosition(s, c);
p = Math.max(p, rightPosition);
set.add(c);
}
}
ans.add(p - lastP);
lastP = p;
p++;
}
return ans;
}
private int getRightPosition(String s, char c) {
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == c) {
return i + 1;
}
}
return 0;
}
执行结果:
查看官方解法
贪心算法+双指针(有待深入理解)