程序员面试金典 - 面试题 01.06. 字符串压缩（字符串）

Michael阿明

发布于 2020-07-13 15:59:55

3760

1. 题目

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/compress-string-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

直接模拟即可

class Solution {
public:
    string compressString(string S) {
    	if(S.size()<2)
    		return S;
    	char prev = S[0];
    	int i, count = 1;
    	string ans;
    	for(i = 1; i < S.size(); ++i)
    	{
    		if(S[i] == prev)
    			count++;
    		else
    		{
    			ans += prev+to_string(count);
    			count = 1;
    			prev = S[i];
    		}
    		if(i == S.size()-1)
    			ans += prev+to_string(count);
			if(ans.size() >= S.size())
				return S;
    	}
    	return ans;
    }
};