Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

My task was to perform a basic string compression by replacing consecutive repeated characters by one instance of the character and integer denoting the number of repetitions. For example the string "aaaaabbcccdeee" should be reduced to "a5b2c3de3". I have tried working in C# using a simple logic. Please see the below code. Also I have added the condition to not to add the count 1 in the compressed string if there is only single letter occurrence. E.g. if letter "d" is occurred only once in a string "aaabbcccdee" then function will give a compressed string as "a3b2c3de2" and not the "a3b2c3d1e2". To modify this requirement we can change the condition for this single count. Please let me know about the comparative time and space complexity and other efficient way in C#.

class StringCompression
{
    static void Main(string[] args)
    {
        StringCompression sc = new StringCompression();

        sc.CompressionMethod("aaaaabbbccdeeeee");
        sc.CompressionMethod("aaabbccdddee");
        sc.CompressionMethod("a");
    }

    public void CompressionMethod(string originalString)
    {
        List<char> OriginalList = new List<char>();
        List<string> CompressedList = new List<string>();
        OriginalList.AddRange(originalString);
        // Convert to Character Array
        char[] charArray = OriginalList.ToArray();

        int i = 0;
        char character;
        int len = charArray.Length;

        while (i < len)
        {
            int n = 0;
            character = (charArray[i]);
            while (i < charArray.Length && charArray[i] == character)
            {
                n = n + 1;
                i++;
            }

            // add characters to the new list 
            CompressedList.Add(character.ToString());

            // add character counts to the new list 
            if (n == 1)
            {
                // Do nothing
            }
            else
            {
                CompressedList.Add(n.ToString());
            }
        }
        // CompressedList will contain compressed string
        foreach (string str in CompressedList)
        {
            Console.Write(str);
        }
        Console.Write("\n");
        Console.Write("\n");
    }
}
share|improve this question
1  
That method is called Run Length Encoding if you're curious for more details. – Michael Todd 9 hours ago

3 Answers 3

String as an Array

You got your string parameter:

string originalString

Then you turned it into a list:

OriginalList.AddRange(originalString);

Then you turned it into an array:

charArray = OriginalList.ToArray();

And finally used it as:

character = (charArray[i]);

Instead of all that, you could have just done this:

character = (originalString[i]);

Class Design

Instantiating a StringCompression class every time you wanna compress a string can be avoided by just declaring the function CompressionMethod as static since the class has no members anyway. So in Main, you only have to do:

StringCompression.CompressionMethod("String here");

Or better: make it an extension method.

String Builder

Instead of a list of strings in:

CompressedList = new List<string>();

You could instead use a String Builder to create the resulting string.

share|improve this answer

Single Responsibility Principle

This method is doing to much. It is compressing the string and writes it to the Console. You can avoid this by returning a string from this method and add another method for doing the output.

General

  • if you would increase i before the inner while loop you will save one iteration of this loop. You don't need to check the character against itself.
    If you change this you need to initialize n with 1.

  • The condition if(n == 1) should be removed because it doesn't add any value. A better way would be to check for n > 1 and if that is true add the count. Here a explaining comment about why this is used would be good.

  • speaking about comments, comments should explain why something is done in the way it is done. Let the code speak for itself about what is done by using descriptive names for variables, methods and classes.

    A comment like

    // add characters to the new list 
    CompressedList.Add(character.ToString());  
    

    does not add value to the code but noise. We clearly see that the character is added to the list, so no need to comment on that.

Other than these points I completely agree with @helix answer.

share|improve this answer

Apart from other reviews I show you an alternative how you can make this really short with LINQ and Regex:

OK, the first solution wasn't perfect. This one will however do it correctly:

var alphabet = Enumerable.Range(97, 26).Select (i => (char)i + "+");
var pattern = "(" + string.Join("|", alphabet) + ")";

var compressed2 =
    Regex.Matches(str, pattern)
    .Cast<Match>().Select (m => new 
    { 
        Char = m.Groups[1].Value[0], 
        Count = m.Groups[1].Value.Length 
    })
    .Aggregate (string.Empty, (result, nextGroup)  => 
        result.ToString() 
        + nextGroup.Char 
        + (nextGroup.Count > 1 ? nextGroup.Count.ToString() : string.Empty));

For:

var str = "aaabbccdddeezbbb";

the result is:

a3b2c2d3e2zb3

  • First get letter groups with regex and their lengths
  • Then aggregate them to the final string
share|improve this answer
    
Matching "(.)\1{0,}" would be even shorter and would work for non-alphabetical characters. – helix 14 hours ago
    
@helix It doesn't work with this pattern. The result is: abcdezb or did you mean a different usage like not with Regex.Matches? – t3chb0t 14 hours ago
    
With "(.)\1{0,}", you'll have to use the matches themselves instead of the match groups. Needs to be modified a little. Roughly like this: ideone.com/GsHIo0 – helix 14 hours ago
    
@helix this is a cool pattern ;-) Would you explain how it works? – t3chb0t 14 hours ago
    
@helix or add it to you answer with an explanation. Especially the \1 is a bit mystery to me. – t3chb0t 14 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.