地址:https://leetcode-cn.com/problems/compress-string-lcci/

题目

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

示例1:

 输入:"aabcccccaaa"
 输出:"a2b1c5a3"

示例2:

 输入:"abbccd"
 输出:"abbccd"
 解释:"abbccd"压缩后为"a1b2c2d1",比原字符串长度更长。

提示:

字符串长度在[0, 50000]范围内。

解题思路

由于传入的字符串长度可能为0,所以这种特殊情况应该直接返回原字符串(无法对其进行压缩)。

由于题目要求是压缩字符串,但是如果“压缩”后的字符串长度没有变短的话,就应该返回原字符串,所以不应该在原字符串上进行修改,所以我定义了一个新的字符串 cpStr 存储压缩后的字符串。

思路很简单,遍历原字符串,取出一个字符串将其追加到 cpStr 末尾,然后对这个字符进行计数,直到遇到下一个不同的字符计数结束,将计数追加到 cpStr 末尾,并重新将计数 count 修改为1,即当前新遇到的字符个数为1,然后再对新遇到的字符计数,循环前述步骤,直到遍历完原字符串。最后跳出循环还应该将最后一个字符的计数值追加到 cpStr 末尾,因为循环内部最后一个字符不会再遇到新的字符,所以虽然对其进行了计数但是并没有将它的个数追加到压缩的字符串的末尾。

最后返回结果用一个条件表达式,判断 cpStr 的长度是否小于原字符串长度,当且仅当小于原字符串长度的时候才将压缩后的 cpStr 返回,否则应返回原字符串。

代码

class Solution {
public:
    string compressString(string str) {
        int length = str.length();//获取字符串长度
        if (length == 0)
            return str;
        string cpStr;//压缩后的字符串
        char c = str[0];
        cpStr += c;
        int count = 0;//计数某一个字符
        for (int i = 0; i < length; i++) {
            if (str[i] == c) {
                count++;
            }
            else {
                if (count > 0) {
                    cpStr += to_string(count);
                    c = str[i];
                    cpStr += c;
                    count = 1;
               }
            }
        }
        cpStr += to_string(count);//追加最后一个字符的个数
        return cpStr.length() < length ? cpStr : str;
    }
};


Leetcode      Leetcode C++

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!