leetcode每日一题：字符串压缩

利刃大大

发布于 2023-04-12 14:14:25

2850

发布于 2023-04-12 14:14:25

面试题 01.06. 字符串压缩

难度简单142

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

示例1:

 输入："aabcccccaaa"
 输出："a2b1c5a3"

示例2:

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

提示：

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

思路一：

用 tmp 来存储新的字符串，用 count 记录重复出现的字符。
一开始对字符串 s 进行遍历，然后将每次第一次出现的字符赋给 tmp，然后判断一下字符串 s[i] == s[i + 1]，若相等则让 count++ ，不相等则将 count 运用一个函数 to_string 转化为字符串然后尾插到 tmp，
然后继续循环，直到遍历结束。

class Solution {
public:
    string compressString(string S) {
        string tmp;
        int count = 1;
        for(int i = 0; i < S.size(); ++i)
        {
            //只将第一次出现的那个附上去，其他的pop掉
            if(count == 1)
                tmp += S[i];

            //若前后两个相同则直接count++
            if(S[i] == S[i+1])
            {
                count++;
            }
            //前后两个不同则将出现的次数尾插到tmp处
            else
            {
                tmp += to_string(count);//使用to_string函数转化为sting类型
                count = 1;
            }
        }
        //将长度短的string返回
        return tmp.size() < S.size() ? tmp : S;
    }
};

思路二：

运用双指针，让 i 指向第一次出现的字符，然后在内层循环让 j 去遍历找到和 i 处不同的字符
若找到了不同的则与思路1一样，将 i 处的字符尾插到 tmp，然后将长度 j - i 转化为字符串尾插到 tmp 后面
然后将 i 移到 j 处，继续循环，直到遍历结束。

class Solution {
public:
    string compressString(string S) {
        int i = 0, j = 0;
        int n = S.size();
        string tmp;
        // 「外层循环」i 指向每个首次出现的字符
        while (i < n) 
        {
            // 「内层循环」j 向前遍历，直到字符串末尾或找到与 s[i] 不同的字符时跳出
            while (j < n && S[i] == S[j])
                j++;

            // 压缩字符串，添加至 tmp
            tmp += S[i];
            tmp += to_string(j - i);

            // 令 i 指向下一个首次出现的字符
            i = j;
        }
        // 对比「压缩字符串」和「原字符串」长度，返回较短的
        return tmp.size() < n ? tmp : S;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode