2
\$\begingroup\$

I recently wrote a function that replaces every white space with '%20', just for fun (and sharping my coding skills). The input string is terminated with extra white spaces, with the length that the string should have after encoding takes place. For example:

input = "Not encoded  " //2 white spaces in the end
output = "Not%20encoded"

Although I was able to implement such encoding in-place, I was still not pleased with the result, specially due to the inner loop that shifts the whole string to the right everytime a white space is found. Here is my solution, written in C#:

    public string encode(string str)
    {
        var array = str.ToCharArray();
        for (int i = 0; i < array.Length; i++) {
            if (array[i] != ' ') continue;

            //switch every char >> 2, from the end of the string to i
            for (int j = array.Length - 1; j > i; j--) {
                array[j] = array[j - 2];                    
            }

            array[i++] = '%';
            array[i++] = '2';
            array[i] = '0';
        }
        return new String(array);
    }

I'm looking for a solution that operates in O(n), possibly performing a single traversal on the input string. Additional feedback on how to improve performance/readability of my function are always very appreciated :)

\$\endgroup\$
4
  • \$\begingroup\$ Have you looked at the StringBuilder class? It does away with your 2nd shift-y for loop. \$\endgroup\$
    – shivsky
    Oct 21, 2013 at 20:58
  • \$\begingroup\$ I have :) But I was trying to optimize space complexity. That's why I performed the string replacements in-place. \$\endgroup\$
    – rla4
    Oct 21, 2013 at 21:01
  • \$\begingroup\$ How come the string already has exactly the right amount of trailing spaces? Do you have special code for that? Doesn't that perform more allocations? \$\endgroup\$
    – svick
    Oct 22, 2013 at 0:29
  • \$\begingroup\$ Maybe my question was not clear enough: this is not a "real world" application nor a "real world" problem. It's just a coding challenge, and the extra trailing spaces is part of the problem specification. \$\endgroup\$
    – rla4
    Oct 22, 2013 at 0:39

3 Answers 3

1
\$\begingroup\$

As strings are immutable you can't really avoid intermediate store of the data as it's being encoded.

As you already know the length of the final string you can avoid the shuffling:

    int spaceCount = 0;
    for (int i = str.Length - 1; str[i] == ' '; i--)
    {
        spaceCount++;
    }
    if (spaceCount == 0) { return str; }

    var array = new char[str.Length];
    int idx = 0;
    for (int i = 0; i < str.Length - spaceCount; i++)
    {
        var current = str[i];
        if (current  == ' ')
        {
            array[idx++] = '%';
            array[idx++] = '2';
            array[idx++] = '0';
        }
        else 
        {
             array[idx++] = current ;
        }
    }

    var encoded = new string(array);

Space required is 2 * O(n) (array and final string) and time is 2 * O(n) (encoding string into array, building final string)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Saying that something is 2 * O(n) doesn't make much sense. You can either calculate how man times some specific operations happens (e.g. 2n array accesses) or you can say that it's O(n), but it doesn't make sense to combine the two. That's because 2 * O(n) means exactly the same thing as O(n). \$\endgroup\$
    – svick
    Oct 22, 2013 at 0:37
  • \$\begingroup\$ @svick: While in the theoretical world O(c * n) = c * O(n) = O(n) and c as a constant doesn't matter, in the practical world reducing c can sometimes be a valuable optimization. So I like to state this factor. \$\endgroup\$
    – ChrisWue
    Oct 22, 2013 at 1:29
  • \$\begingroup\$ Yes, but the factor you're static doesn't say anything unless you explain it. For example, using your counting, 2 * O(n) could easily be faster than O(n). Constants factors are important, but it's very hard to represent them in a way that makes any sense. \$\endgroup\$
    – svick
    Oct 22, 2013 at 9:35
2
\$\begingroup\$

Your solution:

  • copies the whole string twice (1. string.ToCharArray() 2. new string())
  • needs n bytes of extra storage (apart from the input and output; n is the size of the output)
  • potentially moves the characters in the string a lot (O(n2))
  • requires the input to already have free space for the expansion

Solution using StringBuilder:

  • copies the whole string twice (1. calls to Append() 2. StringBuilder.ToString())
  • needs about n bytes of extra storage
  • doesn't need to move characters at all
  • doesn't require the input to be in any special format

Based on this, StringBuilder is clearly the better solution.

But there is even better solution: just use string.Replace(). That's likely going to be quite efficient and it's much shorter than any other of the proposed alternatives.

\$\endgroup\$
1
  • \$\begingroup\$ @downvoter: it would help if you explained what you think is wrong with my answer. \$\endgroup\$
    – svick
    Oct 22, 2013 at 0:25
1
\$\begingroup\$

Here's how I would do it (sans assertions/error checks):

private static string Encode(string input)
{
    var output = new char[input.Length];
    var i = 0;
    var o = 0;

    while (o < output.Length)
    {
        if (input[i] != ' ')
        {
            output[o++] = input[i++];
        }
        else
        {
            output[o++] = '%';
            output[o++] = '2';
            output[o++] = '0';
            ++i;
        }
    }

    return new string(output);
}

It's O(n) in both time and memory.

Using a StringBuilder doesn't gain you much in this instance, because you know exactly how large your output will be (the same length as your input). It's just a wrapper around a char[] anyway, so you'd end up with slightly slower code without any benefit.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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