面试金典0106 字符串压缩

题目：字符串压缩

• 利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）

  # 样例1
  输入："aabcccccaaa"
  输出："a2b1c5a3"
      
  # 样例2
   输入："abbccd"
   输出："abbccd"
   解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
      
  # 提示：
  字符串长度在[0, 50000]范围内。

解题方法：

1. 遍历模拟：两层遍历，内层用while，判断当前字符连续出现了多少个

时间复杂度为O(n)，空间复杂度为O(n)，用于存储生成的字符串

解法一：

1. 强制类型转化：想把int转为对应的字符，不可以用char()，因为这样会转化到对应的ASCII表中的字符，需要用to_string()来转化，转换完为string类型
2. S.push_back(char c)：push_back()函数只能在字符串末尾添加字符，而不能是字符串
3. S.insert(int pos, string s)：insert()函数只能在pos后面添加字符串，而不能是字符。如果pos==S.size()时，可以直接用加号S = S + s就可以了

class Solution {
public:
    string compressString(string S) {
        string S2 = "";
        for(int i=0; i<S.size(); ++i)
        {
            char c = S[i];
            int c_num = 1;
            while(c == S[i+1])
            {
                i++;
                c_num++;
            }
            S2.push_back(c); // 只能push_back(char c) char类型变量
            // cout << S2.size() << (char(c_num)) << "##" << to_string(c_num); // 1##23
##15##57##2 
            S2.insert(S2.size(), to_string(c_num)); // 只能insert(int pos, string s) string类型变量
            // S2 = S2 + to_string(c_num);
        }
        if(S.size() <= S2.size())
            return S;
        return S2;
    }
};