我一开始看数据范围很小,没怎么想就直接暴力了。
暴力的思路是:
对于每一段S的前缀,这个前缀中的每一个字母都不应该在前缀的补集中出现,所以直接循环i:0 to S.length然后对于每一次循环,再循环前缀中的每一个字母,判断是否在后面出现,如果出现就
说明该前缀不合适继续向后循环,如果没有出现就加入到vector里,并且下一次判断前缀时直接从sum(vector) 开始,所以时间复杂度应该是小于 n的。
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> ans;
int len = S.size();
int last = ;
int ex = ;
for(int i=;i<len;i++)
{ for(int j=ex;j<=i;j++)
{
bool p = false;
for(int k=i+;k<len;k++)
{
if(S[j] == S[k]) {
p = true;
break;
}
}
if(p) {
break;
}
if(j == i) {
ans.push_back(i + - ex);
ex = i+;
}
}
}
return ans;
}
};
线性复杂度的思路:
后来觉得这样不太好,其实在读题的时候就隐约觉得有O(n)的解法,所以事后想了一下,在一开始先处理每一种字母最后出现的位置。
然后遍历S时维护一个已遍历前缀中的字母所出现的最大位置,称为lastpos,当遍历到i == lastpos时,说明该前缀中的所有字母都只出现在该前缀。加入vector。
所以时间复杂度是2n
class Solution {
public:
vector<int> partitionLabels(string S) {
vector<int> ans;
int last[];
for(int i=;i<S.size();i++)
{
last[S[i]-'a'] = i;
} int lastpos = , ex = ;
for(int i=;i<S.size();i++)
{
lastpos = max(lastpos, last[S[i]-'a']);
if(lastpos == i) {
ans.push_back(i + - ex);
ex = i + ;
}
}
return ans;
}
};