开始做的时候,就是单个字符这样想,看这个字符是否在当前字符串中。如果在就加入,不在就新建一个字符串,但发现这个思路是错的。
加入的字符改变的是当前字符串截至的位置,即使当前字符不在字符串中,但不意味着后面的字符就没有。
因此本题的关键就是先要找到每个字符的结束位置和每个字符串的结束位置,两个位置相等是就代表着找到了。
找到每个字符的结束位置,这个方法还是很巧妙的,不断更新最后位置
点击查看代码
for(int i=0;i<sz;i++){
lastword[s[i]-'a']=i;
}
点击查看代码
class Solution {
public:
vector<int> partitionLabels(string s) {
int sz=s.size();
vector<int>lastword(26,-1);
for(int i=0;i<sz;i++){
lastword[s[i]-'a']=i;
}
int start=0;int end=0;
vector<int>result;
for(int i=0;i<sz;i++){
end=max(end,lastword[s[i]-'a']);
if(end==i){
result.push_back(end-start+1);
start=i+1;
}
}
return result;
}
};