31/10/2017

[Java] Look and say generator

The count and say sequence is a self describing sequence where given a starting seed, each subsequent element is the concatenation of the number of times a number appeared consecutively in the previous element. For example with seed 1:

1   -> one 1
11 -> two 1
21 -> one 2, one 1

I provide here an implementation to get the nth element given any seed. Unfortunately, we have to compute all elements before getting the one of interest :(

This runs in O(M) space, where M is the length of the resulting string and O(NxM) time. Beware that M is not that small since in the worst case at each new iteration we add one character for each current one, thus doubling the size of the string!

The idea is simply to iterate from 1 to N and for each iteration, loop over all the characters in the partial output string and count the consecutive appearances to form a new partial string.

An improvement could be to identify those special seeds that will always return themselves and skip the calculation, eg: 22 will always be 22 no matter how many iterations we have.

You can check the implementation of lookAndSay on my Gist along with some sample test cases in LookAndSayJTests.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.