I had another programming problem dawn on me the other day;
Given a string of words, separated by spaces, reverse each words’ letters, but not the order of the words in the string.
Sounds simple enough. If you were to have the string “abc defg”, the output would be “cba gfed”. A simplistic brain puzzle, but I admittedly took more time than I thought necessary to solve it.
Assumptions:
- I’d need a method that can reverse a given string
- I’d be manipulating arrays of characters, not actual “strings”
I wrote my first test using those assumptions:
public void CanReverseCharactersOfAString()
{
string testString = "abcdefg";
string expectedOutcome = "gfedcba";
string reversedString = Manipulator.ReverseString(testString);
Assert.AreEqual(expectedOutcome, reversedString);
}
So I wrote this test without writing any other code, and as you can see, it’s expecting a class called “Manipulator” that has a static method “ReverseString”. Yes, I suppose I could have written a string extension method, but I chose not to. No reasoning behind that decision.
Of course, this test will fail because the project won’t build. Let’s go fill in the blanks.
public class Manipulator
{
public static string ReverseString(string s)
{
char[] chars = s.ToCharArray();
ReverseAtIndices(ref chars, 0, chars.Length);
return new string(chars);
}
private static void ReverseAtIndices(ref char[] chars, int low, int high)
{
char temp;
int i = 0; // 'i' will help us get from one side of the string to the other, working backwards
for (int j = low; j < high; j++)
{
int end = high - 1 - i++; // 'end' is the other index to swap letters with
if (j &amp;gt;= end) // if the current index 'j' is greater than or equal to 'end', we can stop swapping
break; //Why? Because we've reached the half-way point in the string.
temp = chars[j];
chars[j] = chars[end];
chars[end] = temp;
}
}
}
I realized I’d need a helper method, ReverseAtIndices, that takes a reference to a character array and then a low and high integer. The character array is the string to be reversed. Low and high are the indices in the array to start and stop the reversing, respectively (so I guess I could refactor and call them “start” and “stop”, eh?)
The method loops through the array and swaps letters at opposite ends of the array. For instance, in the array of [a,b,c], ‘a’ would get swapped with ‘c’, and ‘b’ would get swapped with itself. If we allowed the loop to go just one step further, it would swap ‘a’ and ‘c’ again, outputting [a,b,c] instead of the desired [c language=",b,a"][/c].
Running the test CanReverseCharactersOfAString() passes, so on to the next challenge; reversing letters of words in a string while not changing the order of the words. Let’s write a test for it:
[Row("abc def", "cba fed", ' ')]
[Row("abc", "cba", ' ')]
[Row("abc defg hij kl", "cba gfed jih lk", ' ')]
[Row("hello world!", "olleh !dlrow", ' ')]
public void CanReverseLettersInStringOfWords(string input, string expected, char delimiter)
{
Assert.AreEqual(expected, Manipulator.ReverseLettersInAStringOfWords(input, delimiter));
}
I decided to use MbUnit’s row-testing capabilities so that I could run the same test with differing inputs without having to write more tests.
As you’ll note, I’ve assumed I’m going to have a new static method in the Manipulator class called ReverseLettersInAStringOfWords. Admittedly, not a great name, but, it’s fairly descriptive for this exercise. The method takes just two parameters, a string and a character. The string is, of course, the string of words we want to reverse some letters in, and the character is the delimiter between words. In this exercise, the delimiter will always be a space, but, we could use this method in the future and easily pass in any delimiter we wanted, such as a comma.
When writing the actual method, ReverseLettersInAStringOfWords, I had some difficulty getting it to work in the manner I wanted. I’m pretty sure there are dozens of Google answers out there on this very problem, but, I wanted to solve it without them first. I’ll probably go back and refactor once I see some other solutions. Here’s the code. It’s a little verbose for my liking, but, again, it hasn’t be refactored yet (basically I’m asking for you to turn a blind eye just this once ;) ):
public static string ReverseLettersInAStringOfWords(string s, char delimiter)
{
char[] chars = s.ToCharArray();
char temp;
int i=0;
int low, high;
low = high = i;
for (i = 0; i &amp;lt; chars.Length; i++)
{
// Move the 'high' index up if the delimiter hasn't been found yet
if(chars[i] != delimiter)
high = i + 1;
else
{
ReverseAtIndices(ref chars, low, high);
// Move up the low index now that we've found a delimiter
// and reversed some characters
low = i + 1;
}
}
// The end of the string may not contain a delimiter, so make sure
// we reverse the last set of characters
if(high == chars.Length)
ReverseAtIndices(ref chars, low, high);
return new string(chars);
}
With this method written, all the tests pass (thankfully) and we’ve satisfied the guidelines of the problem statement.
Now I’m off to Google some better alternatives :)
