Leetcode 字符串压缩

Leetcode简单面试题

请注意,本文编写于 555 天前,最后修改于 555 天前,其中某些信息可能已经过时。

做道简单的题放松一下。。。

题目

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

示例1:

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

示例2:

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

提示:

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

思路

设置两个标记,和一个临时存放结果的字符串temp,分别为pre和last,pre指向当前的字母并将其附在temp尾部,last往后搜索相同的字母,直到遇到不同字符或者字符串尾部才停止,然后另last-pre得到相同连续字符的个数,并附在temp尾部,并重复前面的步骤。

代码

class Solution {
public:
    string compressString(string S) {
        if (S.length()==0||S.length()==1) {
            return S;
        }
        string temp = "";
        int pre = 0, last = 0;
        while (last<S.length()) {
            temp += S[pre];
            while (last<S.length() && S[last]==S[pre]) {
                last++;
            }
            temp += to_string(last - pre);
            pre = last;
        }
        return temp.length() >= S.length() ? S : temp;
    }
};

额外:中间一开始使用了temp = temp + to_string(last - pre),提示超出内存限制,是在字符串很大的情况下,改用temp += to_string(last - pre)后便没有了问题,了解之后,前者会另开辟空间,存储temp + to_string(last - pre)的值,再赋值给temp,而后者相当于直接append到temp字符串上。

此处评论已关闭