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) );
        }


        Console.ReadLine();
    }

    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.

No comments:

Post a Comment