Reverse a String without using Reverse. It works, but why?

Question

Ok, so a friend of mine asked me to help him out with a string reverse method that can be reused without using String.Reverse (it's a homework assignment for him). Now, I did, below is the code. It works. Splendidly actually. Obviously by looking at it you can see the larger the string the longer the time it takes to work. However, my question is WHY does it work? Programming is a lot of trial and error, and I was more pseudocoding than actual coding and it worked lol.

Can someone explain to me how exactly reverse = ch + reverse; is working? I don't understand what is making it go into reverse :/

class Program
{

    static void Reverse(string x)
    {

        string text = x;
        string reverse = string.Empty;
        foreach (char ch in text)
        {

            reverse = ch + reverse;
            // this shows the building of the new string. 
            // Console.WriteLine(reverse);
        }

        Console.WriteLine(reverse);        

    }
    static void Main(string[] args)
    {

        string comingin;
        Console.WriteLine("Write something");
        comingin = Console.ReadLine();
       Reverse(comingin);

        // pause
        Console.ReadLine();
    }



}

Have you tried walking through it on paper, or in the debugger? Any answer is basically going to do the same thing, I'd imagine... — Jon Skeet
– Jon Skeet, Commented Jun 6, 2013 at 12:41
What you are basically doing is inserting each letter of the original string at position 0 in the new string. — Rotem
– Rotem, Commented Jun 6, 2013 at 12:42
What's not to understand? You take characters from the front of x and prepend them to the result reverse - so abc becomes (a bc), (ba c) (cba ``) — user594138
– user594138, Commented Jun 6, 2013 at 12:43
I've been up for something like 32 hours so I had no idea how this was working...for me it was one of those situations that it was just working and I was satisfied with the immediate result since it was literally just me trying to pseudocode it out before I actually wrote anything. I was expecting to need an array lol. — Randy E
– Randy E, Commented Jun 6, 2013 at 12:45
You should use StringBuilder since concatenating strings is expensive. — Dustin Kingen
– Dustin Kingen, Commented Jun 6, 2013 at 12:49

Colm Prunty · Accepted Answer · 2013-06-06 12:43:21Z

2

If the string passed through is "hello", the loop will be doing this:

reverse = 'h' + string.Empty

reverse = 'e' + 'h'

reverse = 'l' + 'eh'

until it's equal to

olleh

answered Jun 6, 2013 at 12:43

Colm Prunty

1,6401 gold badge14 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Randy E Over a year ago

Thanks for the response, all 3 were spot on responses but this one starts it out at string.Empty which I think is just a little more detailed but to the point than the other 2. All good response, but I'll be marking this one as the answer once it allows me to...apparently you can't mark answers for a certain amount of time lol.

DonBoitnott · Accepted Answer · 2013-06-06 12:43:26Z

2

If your string is My String, then:

Pass 1, reverse = 'M'
Pass 2, reverse = 'yM'
Pass 3, reverse = ' yM'

You're taking each char and saying "that character and tack on what I had before after it".

answered Jun 6, 2013 at 12:43

DonBoitnott

11.1k7 gold badges53 silver badges70 bronze badges

Comments

Rick Davin · Accepted Answer · 2013-06-06 13:23:38Z

2

I think your question has been answered. My reply goes beyond the immediate question and more to the spirit of the exercise. I remember having this task many decades ago in college, when memory and mainframe (yikes!) processing time was at a premium. Our task was to reverse an array or string, which is an array of characters, without creating a 2nd array or string. The spirit of the exercise was to teach one to be mindful of available resources.

In .NET, a string is an immutable object, so I must use a 2nd string. I wrote up 3 more examples to demonstrate different techniques that may be faster than your method, but which shouldn't be used to replace the built-in .NET Replace method. I'm partial to the last one.

    // StringBuilder inserting at 0 index
    public static string Reverse2(string inputString)
    {
        var result = new StringBuilder();
        foreach (char ch in inputString)
        {
            result.Insert(0, ch);
        }
        return result.ToString();
    }

    // Process inputString backwards and append with StringBuilder
    public static string Reverse3(string inputString)
    {
        var result = new StringBuilder();
        for (int i = inputString.Length - 1; i >= 0; i--)
        {
            result.Append(inputString[i]);
        }
        return result.ToString();
    }

    // Convert string to array and swap pertinent items
    public static string Reverse4(string inputString)
    {
        var chars = inputString.ToCharArray();
        for (int i = 0; i < (chars.Length/2); i++)
        {
            var temp = chars[i];
            chars[i] = chars[chars.Length - 1 - i];
            chars[chars.Length - 1 - i] = temp;
        }
        return new string(chars);
    }

answered Jun 6, 2013 at 13:23

Rick Davin

1,0418 silver badges11 bronze badges

3 Comments

Randy E Over a year ago

Rick you're right, the spirit of the task for him was to learn about the reverse function without using it. Many academic institutes do these types of things so developers understand why their code works rather than just writing the code. In my situation I just wrote the code and I was not sure why it was working (which is the point of the exercise! lol) I haven't had any formal programming education, I'm all self taught, so when something works that I'm not sure why I have to seek outside resources :) Thanks for the additional examples.

Rick Davin Over a year ago

I just tested various methods. My Reverse4() method is by far the fastest. It's about twice as fast as stepping backwards through the original string and appending to a StringBuilder object, which is the equivalent of @CodeCamper's ReverseFast method.

JARRRRG Over a year ago

I'm an 'experienced' developer. I just got asked to demonstrate this in an IDE on an interview and absolutely bottled it. This answer is the one.

Piotr Czarnecki · Accepted Answer · 2013-06-06 12:45:51Z

1

Please imagine that you entrance string is "abc". After that you can see that letters are taken one by one and add to the start of the new string:

reverse = "", ch='a' ==> reverse (ch+reverse) = "a"
reverse= "a", ch='b' ==> reverse (ch+reverse) = b+a = "ba"
reverse= "ba", ch='c' ==> reverse (ch+reverse) = c+ba = "cba"

answered Jun 6, 2013 at 12:45

Piotr Czarnecki

1,6983 gold badges14 silver badges22 bronze badges

Comments

CodeCamper · Accepted Answer · 2013-06-06 13:33:44Z

1

To test the suggestion by Romoku of using StringBuilder I have produced the following code.

   public static void Reverse(string x)
        {
            string text = x;
            string reverse = string.Empty;
            foreach (char ch in text)
            {
                reverse = ch + reverse;
            }
            Console.WriteLine(reverse);
        }

        public static void ReverseFast(string x)
        {
            string text = x;
            StringBuilder reverse = new StringBuilder();
            for (int i = text.Length - 1; i >= 0; i--)
            {
                reverse.Append(text[i]);
            }             
            Console.WriteLine(reverse);
        }

        public static void Main(string[] args)
        {
            int abcx = 100; // amount of abc's
            string abc = ""; 
            for (int i = 0; i < abcx; i++)
                abc += "abcdefghijklmnopqrstuvwxyz";
            var x = new System.Diagnostics.Stopwatch();
            x.Start();
            Reverse(abc);
            x.Stop();
            string ReverseMethod = "Reverse Method: " + x.ElapsedMilliseconds.ToString();
            x.Restart();
            ReverseFast(abc);
            x.Stop();
            Console.Clear();
            Console.WriteLine("Method | Milliseconds");
            Console.WriteLine(ReverseMethod);
            Console.WriteLine("ReverseFast Method: " + x.ElapsedMilliseconds.ToString());
            System.Console.Read();
        }

On my computer these are the speeds I get per amount of alphabet(s).

100 ABC(s) Reverse ~5-10ms FastReverse ~5-15ms

1000 ABC(s) Reverse ~120ms FastReverse ~20ms

10000 ABC(s) Reverse ~16,852ms!!! FastReverse ~262ms

These time results will vary greatly depending on the computer but one thing is for certain if you are processing more than 100k characters you are insane for not using StringBuilder! On the other hand if you are processing less than 2000 characters the overhead from the StringBuilder definitely seems to catch up with its performance boost.

answered Jun 6, 2013 at 13:33

CodeCamper

7,0148 gold badges49 silver badges101 bronze badges

2 Comments

Randy E Over a year ago

Thank you for that example. I was just playing around with this to see how it would be implemented. Something to add to the toolbox.

CodeCamper Over a year ago

Anytime! StringBuilder really is useless for a small sentence. But suppose the user wanted to reverse Encyclopædia Britannica you would really feel sick for not using StringBuilder!

Collectives™ on Stack Overflow

Reverse a String without using Reverse. It works, but why?

5 Answers 5

1 Comment

Comments

3 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related