CareerCup1.5.cpp

CareerCup1.5.cpp

/* Chapter 1
 * 1.5 Write a method to perform basic string compression using the counts of repeated characters
 * Example: "aabcccccaaa"
 *        =>"a2b1c5a3"
 * If "compressed" string would not become smaller than the original string ("abc" => "a1b1c1"), your method should
 * return the original string. Assume the string has only upper and lower case letters (a~z)
 */

#include <iostream>
#include <string>

using namespace std;

/* Pure char array operation version */
char* str_compress1(char* str)
{
    // Calculate # of each char sub-block
    int count[strlen(str)];
    int j = 0;  // index for count[]
    memset(count, 0, sizeof(count));  // initialize to 0
    // Iterate to count
    for (int i = 0; i < strlen(str); ++i)
    {
        if (i == 0)
        {
            count[j]++;
        }
        else if (str[i] == str[i - 1])
        {
            count[j]++;
        }
        else if (str[i] != str[i - 1])
        {
            count[++j]++;
        }
    }
    // Resize count[]
    count[j + 1] = '\0';
    // For single digit number of char
    int new_len = 2 * (j + 1);
    // Recalculate to support test cases which make count[index] a double digit num
    for (int i = 0; i < j + 1; ++i)
    {
        if (count[i]/10 != 0)
        {
            new_len++;
        }
    }
    // new >= old, return old
    if (new_len >= strlen(str))
        return str;
    // new < old, compress, return new
    else
    {
        char* compr_str = new char[new_len];
        char* p = compr_str;  // point to current write position
        j = 0;  // clear count[] index and use again
        for (int i = 0; i < strlen(str); ++i)
        {
            if (i == 0)
            {
                *p++ = str[i];
                if (0 < count[j] && count[j] < 10)
                {
                    *p++ = (char)((int)'0' + count[j++]);
                }
                else if (10 <= count[j] && count[j]< 100)
                {
                    *p++ = (char)((int)'0' + count[j] / 10);
                    *p++ = (char)((int)'0' + count[j++] % 10);
                }
            }
            else if (str[i] != str[i - 1])
            {
                *p++ = str[i];
                if (0 < count[j] && count[j] < 10)
                {
                    *p++ = (char)((int)'0' + count[j++]);
                }
                else if (10 <= count[j] && count[j] < 100)
                {
                    *p++ = (char)((int)'0' + count[j] / 10);
                    *p++ = (char)((int)'0' + count[j++] % 10);
                }
            }
        }
        return compr_str;
    }
}

/* Utilized string version*/
string str_compress2(string old)
{
    string new_str;
    size_t length = old.length(); 
    if (length > 0) 
    {
        // Assign the first char
        char buf = old[0];
        int cnt = 1;
        for (size_t i = 1; i < length; ++i)
        {
            if (old[i] != buf)
            {
                // New char encountered
                // Concatenate previous char and its counter
                new_str = new_str + buf + to_string(cnt);
                // Store current char
                buf = old[i];
                // Reset cnt to 1
                cnt = 1;
            }
            else
                ++cnt;
        }
        // Append the last char and its counter
        new_str = new_str + buf + to_string(cnt);
    }
    // Determine return value
    return new_str.size() >= old.size() ? old : new_str;
}

int main(int argc, char const *argv[])
{
    string s = "AAAoooooooooooXe";
    cout << str_compress2(s) << endl;
    return 0;
}