Algorithmathon Day 12: String First Non-repeated CharacterCreated: 26 July 2013 Modified:
This entry starts a period of string manipulation. Today’s goal will be to return the first non-repeated character in a string. Ruby provides us with a String class that will be easy to subclass. If we have string “ABABCAB” we want to find the letter “C”. One way to approach this is to compare every letter in the string to every other letter in the string. This however would have a n2 cost. If we shortened the string by one character on each pass we could reduce that to n * (n-1). Faster but still effectively n2. If however we use a hash to track and count the letters we can reduce this to n + 26. In this case we are assuming the use of only A through Z. Let’s jump right into the initial RSpec tests.
A very basic class will satisfy these tests.
Now we need something with more substance so lets build some additional tests and the code to satisfy them.
We now have a working method that gives us a solution. Next time we will be adding a method which removes characters from a string.tags: Algorithm - Algorithmathon - RSpec - Ruby - String