A Journey 2 Eternity

Basic string compression using the counts of repeated characters

Posted on: July 13, 2012

Implement a method to perform basic string compression using the counts of repeated characters. For example string “aabcccccaaa” would become “a2b1c5a3“. If the compressed string would not become smaller then original string then return the original string.

 int CountCompression(string str)
{
	char last = str.at(0);
	int size = 0, count = 1;

	for (int i = 1; i < str.length(); i++)
	{
		if(str.at(i) == last) {
			count++;
		} else {
			last = str.at(i);
			size += 1 + to_string(count).length();
			count = 1;
		}
	}

	// we need to count the very last set of repeated character sets
	size += 1 + to_string(count).length();

	return size;
}

string Compress(string str)
{
	int size = CountCompression(str);
	if(size >= str.length())
		return str;

	string compressStr;
	char last = str.at(0);
	int count = 1;

	for (int i = 1; i < str.length(); i++)
	{
		if (str.at(i) == last) {
			count++;
		} else { // insert char count and update the last char
			compressStr += last;
			compressStr += to_string(count);
			last = str.at(i);
			count = 1;
		}
	}

	// we need to update the very last set of repeated character sets
	compressStr += last;
	compressStr += to_string(count);

	return compressStr;
}
Advertisements
Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Pages

Categories

July 2012
M T W T F S S
« Jun   Aug »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Blog Stats

  • 26,880 hits
%d bloggers like this: