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 IEnumerableStringRotations(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