Reverse a String with No Loops

Back to Listing

Reverse a String with No Loops


05 Oct, 2011


class Program  
{
    static void Main(string[] args)
    {
        var input = "this is a stupid interview question";
        var output = new string(new Stack<char>(input).ToArray());

        Console.WriteLine(output);
        Console.ReadKey();
    }
}

Was stuck in my head, so I had to get it out.

Zames pointed out in the comments for this post that the title should be "Reverse a String with No Explicit Loops" and he is absolutely correct. There are at least two places in the code that are potentially using using loops behind the scene.

The first is my conversion from string to a stack. In my code I simply pass the constructor of stack the string, but what does the constructor do with that string to make it a stack? Using the Resharper decompiler, we can check.

public Stack(IEnumerable<T> collection)  
{
  if (collection == null)
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  ICollection<T> collection1 = collection as ICollection<T>;
  if (collection1 != null)
  {
    int count = collection1.Count;
    this._array = new T[count];
    collection1.CopyTo(this._array, 0);
    this._size = count;
  }
  else
  {
    this._size = 0;
    this._array = new T[4];
    foreach (T obj in collection)
      this.Push(obj);
  }

The specific constructor that I was using simply copies the underlying array if the IEnumerable passed in happens to also be an ICollection otherwise it for loops the collection.

The second place this implementation hides a loop is in the ToArray method.It's implementation looks like this:

public T[] ToArray()  
{
  T[] objArray = new T[this._size];
  for (int index = 0; index < this._size; ++index)
    objArray[index] = this._array[this._size - index - 1];
  return objArray;
}

And we have another loop. Ryan Farley points out in the comments that this puzzle could be accomplished by using the Reverse method found on Array. He provides an example as well. It is interesting that the ToArray method does not use Array.Reverse. Looking at the rest of the stack class, the CopyTo method does use Array.Reverse. I wonder why there is a difference. Both methods create new arrays.

But does Array.Reverse actually have some magic implementation that avoids a loop?

public static void Reverse(Array array, int index, int length)  
{
  if (Array.TrySZReverse(array, index, length))
    return;
  int index1 = index;
  int index2 = index + length - 1;
  object[] objArray = array as object[];
  if (objArray != null)
  {
    for (; index1 < index2; --index2)
    {
      object obj = objArray[index1];
      objArray[index1] = objArray[index2];
      objArray[index2] = obj;
      ++index1;
    }
  }
  else
  {
    for (; index1 < index2; --index2)
    {
      object obj = array.GetValue(index1);
      array.SetValue(array.GetValue(index2), index1);
      array.SetValue(obj, index2);
      ++index1;
    }
  }
}

Looks like it uses some loops as well. But what about the TrySZReverse method? What is that about? Class is starting, I'll have to dig in later.

Share this story

Bobby Johnson

About Author

I am a passionate engineer with an interest in shipping quality software, building strong collaborative teams and continuous improvement of my skills, team and the product.

comments powered by Disqus
Back to top