In a recent job interview I was asked to write a simple C# function that would reverse a string and return the result. However, there was a catch, I was unable to use the provided string objects ‘reverse()’ function. I successfully created a function that did as requested (using a decrementing for-loop and concatenation), though I realised that using concatenation would result in a new string being created in memory upon each iteration - as strings are immutable objects. I solved this by using a StringBuilder to append each character to and returning the result. On the way home I began to think of the endless ways in which you could reverse a string in code (extremely sad I know).
1: Decrementing for-loop with concatenation
The original way that I achieved the intended result was to use a decrementing for-loop that appended each character of the input to a new string in reverse order. I was able to access the parsed strings individual characters similar to the way you would reference an array’s items.
2: Incrementing/decrementing for-loop with two arrays
Another way I formed to reverse a string was to create an empty array and iterate over the length of the string with both incrementing/decrementing counters. The array position uses the incrementing counter where as the parsed in string uses the decrementing one. Finally the created array is joined into a single string and returned.
3: Incrementing for-loop with array pushing and charAt
The above example is a modification of the second example. Instead of using two counters however we use one incrementing value that gets deducted from the total length of the parsed in string. This calculated value determines the position of the next character to be pushed onto the new array (using the ‘push()’ function instead of ‘’). The other difference from the last example is that it uses the strings ‘charAt()’ method instead of its array capabilities.
4: In-built functions
This implementation takes advantage of the ‘reverse()’ method provided by the Array prototype. First it splits the string into a real array, then calls the ‘reverse()’ method and finally returns the joined array.
5: Decrementing while-loop with concatenation and substring
Using a decrementing while-loop I was able to implement this method. Again harnessing concatenation, I was able to achieve the iteration through the string in a similar fashion to the for-loop used in the first two examples. I was then able to use the strings ‘substring()’ function to retrieve each desired character.
6: Single for-loop declaration with concatenation
This is most likely my favorite implementation, due to its unnecessary cryptic nature. Using only a single for-loops parameters, I was able to decrement through the parsed in string and concatenate each character to a new string to return.
7: Recursion with substring and charAt
The above example recursively calls itself, passing in the inputted string, excluding the first character on each iteration, which is instead appended to the result. Iterating through this process until no input is present (the base case) results in a reversed string.
8: Internal function recursion
This is another example of using recursion to reverse a string. The implementation above uses an internal function, which is first called by the outer function, parsing in the inputted string, its length and an empty string. The internal function is then recursively called by itself until the string length has been decremented to zero - at which time the originally empty parsed in string has been concatenated with the inputted string characters in reverse.
9: Half-index switch for-loop
I found this method to be a very effective way of reversing a string, highlighting its benefits when processing large strings. The strings half-point is first calculated and then iterated over. Upon each iteration the upper half’s value (calculated by deducting the current position by the string length) is temporary stored and replaced by the lower half’s value. The temporary value then replaces the lower half’s value to finally result in a reversed string.
10: Half-index recursion
The final method I wish to show uses the same ideology as the last implementation (half-indexing) but instead relies on recursion to reverse the string instead of a for-loop.
A graph showing the performance of the ten implementations in four browsers
Best performing implementation(s) per browser
- Chrome 15 - Implemations 1 and 6
- Firefox 7 - Implementation 6
- IE 9 - Implementation 4
- Opera 12 - Implementation 9
To conclude, I feel upon reflection of the processed data that the first implementation is the most favorable one to use in production as it consistently scores well on each of the browsers. I am surprised by this conclusion as I thought that string concatenation was a costly action to carry out, especially on multiple iterations. This analyse leads me to believe that browser venders have carried out heavy optimization on this process, as its such a common place task.