Wednesday, October 13, 2010

Is Rotation?

I noticed an "interview question" that was posted on StackOverflow awhile ago. It's not particularly complicated -- basically asking "given two strings, how to tell if one is the rotated version of the other?"

Some discussion in the question deals with various faster methods, but the simplest answer is a Python version:

def isrotation(s1, s2):
    return len(s1) == len(s2) and s1 in 2*s2

If we wanted to implement this in Factor, we might want to consider using "short circuit" combinators (which will apply a series of boolean tests and stop on the first test that fails). We will also use the convention that a word? (ending in a "?") returns a boolean.

: rotation? ( s1 s2 -- ? )
    { [ [ length ] bi@ = ] [ dup append subseq? ] } 2&& ;

We can test it, to make sure it works:

( scratchpad ) "stack" "tacks" rotation? .

( scratchpad ) "foo" "bar" rotation? .

Since strings are sequences of characters and this solution uses sequence operations (length, append, and subseq?), it is already generalized to operate on other types of sequences. For example, arrays:

( scratchpad ) { 1 2 3 } { 2 3 1 } rotation? .

So, the next time you get this question in an interview, maybe you can solve it in Factor!

No comments: