The code is pretty simple if we go ahead with using recursion. I started with an iterative solution but quickly realised I am dealing with a list of numbers, going through the numbers one at a time. This is the prerequisite of solving a recursive problem.
The Recursive Solution:
The condition is that the input string will have at least one number, otherwise it won’t make any sense. Though we are not dealing with erroneous input here.
The recursive solution is just so easy on the eye and on the mind:
- We start with the first character, and if the remaining string is empty then return that character and it’s count.
- If we the new character is same as the previous character, then update the count and recursively solve for the remanining substring.
- If the new character is different than the previous character, then add the count of this character to the recursive solution of the rest of the string.
Since c# doesn’t support tail recursion, a lot of the calls in the
else-if clause cannot be optimised, nor can we do anything about the
Running this on my machine for 50 iterations of
sends CPU and memory usage through the roof (100% usage of 1 core and
nearly 900MB of RAM before I stop it after 15 seconds or so). Ouch!
Back to iteration:
Honestly, the iterative solution is not that bad. We create a string of the number and counts and fill it when we detect a change in the current number-character, or at the end of the input.
This runs through the 50 iterations in a couple of seconds on my machine.
The code is present at github.
Author Tushar Tyagi
LastMod Jan 26, 2017