1.5

压缩字符串， 字符串"aabccccaaa"变成"a2b1c5a3",如果没有变短则，返回原字符串

* //O(n) time, O(n) space

* 代码

string compression(string s){
if(s.empty() || s.length()==0) return "";

string ret;
int cnt=0; //记录每个字符的重复次数
char cur;

for(int i=0;i<s.length();i++){
if(cnt==0)
cur=s[i];
++cnt;

if(i+1==s.size() || s[i+1]!=cur){
ret.push_back(cur);
ret+=itoa2(cnt);
cnt=0;
}
}

return ret.size()<s.size()?ret :s;
}

int main(int argc, char *argv[])
{
cout << compression("aabcccccaaa") << endl;
cout << compression("abcad") << endl;
cout << compression("abcadd") << endl;

cout << compression("aaaaaaaaaaa") << endl;
cout << compression("a") << endl;
return 0;
}

1.5

压缩字符串， 字符串"aabccccaaa"变成"a2b1c5a3",如果没有变短则，返回原字符串

* //O(n) time, O(n) space

* 代码

string compression(string s){
if(s.empty() || s.length()==0) return "";

string ret;
int cnt=0; //记录每个字符的重复次数
char cur;

for(int i=0;i<s.length();i++){
if(cnt==0)
cur=s[i];
++cnt;

if(i+1==s.size() || s[i+1]!=cur){
ret.push_back(cur);
ret+=itoa2(cnt);
cnt=0;
}
}

return ret.size()<s.size()?ret :s;
}

int main(int argc, char *argv[])
{
cout << compression("aabcccccaaa") << endl;
cout << compression("abcad") << endl;
cout << compression("abcadd") << endl;

cout << compression("aaaaaaaaaaa") << endl;
cout << compression("a") << endl;
return 0;
}