## Thursday, April 1, 2010

### My stackoverflow answer on: Check if string is a rotation of other string

Found a curious puzzle on stackoverflow, how to check if the string is a rotation of another string.

My provided answer uses the modulo approach.  Hats off to the voted answer(uses concatenation approach), it's the best, I think even Jon Skeet was impressed :-)

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsRotation
{
class Program
{
static void Main(string[] args)
{

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));

string strToTestFrom = "stackoverflow";
foreach(string s in StringRotations(strToTestFrom))
{
Console.WriteLine("is {0} rotation of {1} ? {2}",
s, strToTestFrom,
IsRotation(strToTestFrom, s) );
}

}

public static IEnumerable StringRotations(string src)
{
for (int i = 0; i < src.Length; ++i)
{
var sb = new StringBuilder();
for (int x = 0; x < src.Length; ++x)
sb.Append(src[(i + x) % src.Length]);

yield return sb.ToString();
}
}

public static bool IsRotation(string a, string b)
{
if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
foreach(int ndx in IndexList(a, b[0]))
{
int i = ndx;
if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
return true;
}
return false;
}

public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}

}//class Program
}//namespace IsRotation
```

Output:

```Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True
```

The accepted answer(hint already included in the question itself) is kinda cool, it concatenates the source string to itself, all the possible rotation is inside the concatenated string.