## Algorithmathon Day 14: String Manipulations

Created: 2 August 2013  Modified:

Today’s goal will be to write algorithms for a few different types of string manipulations. Our first goal will be to remove all characters, in an array, from a string. The second will be to reverse all of the characters in a string. Third will be to convert a string to an integer. Finally we will end with converting an integer to a string. The Ruby String class already has some methods that cover this functionality. We will pretend that the do not exist and write our own.

To solve our first problem we will use a straight linear approach which will have a cost at worst of the length of the string times the length of the array. Depending on how Array#include is implemented it might be as low as just the length of the array. Though this would incur additional storage costs.

To reverse all of the characters in a string we will utilize recursion. By counting down from the outside in we will have a cost of log(n).

Our third goal can be achieved by converting each character in the string to its ordinal value. These values start with 48 for “0” on up to “9”. Thus if we subtract 48 we have the numeric value represented by the character. Then we just have to multiply it by 10 raised to the power of the character position starting from the right.

The final method is the reverse of our third goal. We will use division and modulus to break apart our number. When we add 48 to it we will have the ordinal value of our characters. Then we simply need to concatenate the characters together.

Of course we must have our RSpec tests done first.

algorithm_string_spec.rb

The code to satisfy our tests.

algorithm_string.rb

If you want to earn bonus points convert the fourth method to utilize StringIO. This would lessen the overhead of string concatenation.

tags: Algorithm - Algorithmathon - RSpec - Ruby
Less Is More