A friend of mine was asked the following question today at interview for the position of software developer:
Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?
Example:
If s1 = "stackoverflow" then the following are some of its rotated versions:
"tackoverflows"
"ackoverflowst"
"overflowstack"
where as "stackoverflwo" is not a rotated version.
The answer he gave was:
Take
s2and find the longest prefix that is a sub string ofs1, that will give you the point of rotation. Once you find that point, breaks2at that point to gets2aands2b, then just check ifconcatenate(s2a,s2b) == s1
It looks like a good solution to me and my friend. But the interviewer thought otherwise. He asked for a simpler solution. Please help me by telling how would you do this in Java/C/C++ ?
Thanks in advance.
Here's one using regex just for fun:
boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
You can make it a bit simpler if you can use a special delimiter character guaranteed not to be in either strings.
boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
You can also use lookbehind with finite repetition instead:
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
And now for something completely different.
If you want a really fast answer in some constrained context when strings are not rotation of one another
Agreed, it can fail, but it is very fast to say if strings don't match and if they match you can still use another algorithm like string concatenation to check.
As no one has given a C++ solution. here it it:
bool isRotation(string s1,string s2) {
string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
Take each character as an amplitude and perform a discrete Fourier transform on them. If they differ only by rotation, the frequency spectra will be the same to within rounding error. Of course this is inefficient unless the length is a power of 2 so you can do an FFT :-)
Join string1 with string2 and use KMP algorithm to check whether string2 is present in newly formed string. Because time complexity of KMP is lesser than substr.
Another python example (based on THE answer):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
Reverse one of the strings. Take the FFT of both (treating them as simple sequences of integers). Multiply the results together point-wise. Transform back using inverse FFT. The result will have a single peak if the strings are rotations of each other -- the position of the peak will indicate by how much they are rotated with respect to each other.
I guess its better to do this in Java:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
In Perl I would do:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}
or even better using the index function instead of the regex:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
Here is an O(n) and in place alghoritm. It uses < operator for the elements of the strings. It's not mine of course. I took it from here (The site is in polish. I stumbled upon it once in the past and I couldn't find something like that now in English, so I show what I have :)).
bool equiv_cyc(const string &u, const string &v)
{
int n = u.length(), i = -1, j = -1, k;
if (n != v.length()) return false;
while( i<n-1 && j<n-1 )
{
k = 1;
while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
if (k>n) return true;
if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
}
return false;
}
Another Ruby solution based on the answer:
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
C#:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
int rotation(char *s1,char *s2)
{
int i,j,k,p=0,n;
n=strlen(s1);
k=strlen(s2);
if (n!=k)
return 0;
for (i=0;i<n;i++)
{
if (s1[0]==s2[i])
{
for (j=i,k=0;k<n;k++,j++)
{
if (s1[k]==s2[j])
p++;
if (j==n-1)
j=0;
}
}
}
if (n==p+1)
return 1;
else
return 0;
}
I'd do this in Perl:
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
As others have submitted quadratic worst-case time complexity solution, I'd add a linear one (based on the KMP Algorithm):
bool is_rotation(const string& str1, const string& str2)
{
if(str1.size()!=str2.size())
return false;
vector<size_t> prefixes(str1.size(), 0);
for(size_t i=1, j=0; i<str1.size(); i++) {
while(j>0 && str1[i]!=str1[j])
j=prefixes[j-1];
if(str1[i]==str1[j]) j++;
prefixes[i]=j;
}
size_t i=0, j=0;
for(; i<str2.size(); i++) {
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
for(i=0; i<str2.size(); i++) {
if(j>=str1.size()) return true;
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
return false;
}
Why not something like this?
//is q a rotation of p?
bool isRotation(string p, string q) {
string table = q + q;
return table.IndexOf(p) != -1;
}
Of course, you could write your own IndexOf() function; I'm not sure if .NET uses a naive way or a faster way.
Naive:
int IndexOf(string s) {
for (int i = 0; i < this.Length - s.Length; i++)
if (this.Substring(i, s.Length) == s) return i;
return -1;
}
Faster:
int IndexOf(string s) {
int count = 0;
for (int i = 0; i < this.Length; i++) {
if (this[i] == s[count])
count++;
else
count = 0;
if (count == s.Length)
return i - s.Length;
}
return -1;
}
Edit: I might have some off-by-one problems; don't feel like checking. ;)
I like THE answer that checks if s2 is a substring of s1 concatenated with s1.
I wanted to add an optimization that doesn't lose its elegance.
Instead of concatenating the strings you can use a join view (I don't know for other language, but for C++ Boost.Range provide such kind of views).
As the check if a string is a substring of another has linear average complexity (Worst-case complexity is quadratic), this optimization should improve the speed by a factor of 2 in average.
Opera's simple pointer rotation trick works, but it is extremely inefficient in the worst case in running time. Simply imagine a string with many long repetitive runs of characters, ie:
S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2
S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1
The "loop until there's a mismatch, then increment by one and try again" is a horrible approach, computationally.
To prove that you can do the concatenation approach in plain C without too much effort, here is my solution:
int isRotation(const char* s1, const char* s2) {
assert(s1 && s2);
size_t s1Len = strlen(s1);
if (s1Len != strlen(s2)) return 0;
char s1SelfConcat[ 2 * s1Len + 1 ];
sprintf(s1SelfConcat, "%s%s", s1, s1);
return (strstr(s1SelfConcat, s2) ? 1 : 0);
}
This is linear in running time, at the expense of O(n) memory usage in overhead.
(Note that the implementation of strstr() is platform-specific, but if particularly brain-dead, can always be replaced with a faster alternative such as the Boyer-Moore algorithm)
Not sure if this is the most efficient method, but it might be relatively interesting: the the Burrows-Wheeler transform. According to the WP article, all rotations of the input yield the same output. For applications such as compression this isn't desirable, so the original rotation is indicated (e.g. by an index; see the article). But for simple rotation-independent comparison, it sounds ideal. Of course, it's not necessarily ideally efficient!
EDIT: The accepted answer is clearly more elegant and efficient than this, if you spot it. I left this answer as what I'd do if I hadn't thought of doubling the original string.
I'd just brute-force it. Check the length first, and then try every possible rotation offset. If none of them work out, return false - if any of them does, return true immediately.
There's no particular need to concatenate - just use pointers (C) or indexes (Java) and walk both along, one in each string - starting at the beginning of one string and the current candidate rotation offset in the second string, and wrapping where necessary. Check for character equality at each point in the string. If you get to the end of the first string, you're done.
It would probably be about as easy to concatenate - though probably less efficient, at least in Java.
It's very easy to write in PHP using strlen and strpos functions:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
I don't know what strpos uses internally, but if it uses KMP this will be linear in time.
Surely a better answer would be, "Well, I'd ask the stackoverflow community and would probably have at least 4 really good answers within 5 minutes". Brains are good and all, but I'd place a higher value on someone who knows how to work with others to get a solution.
Nobody offered a modulo approach yet, so here's one:
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", "tackoverflwos"));
Console.ReadLine();
}
public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);
if (b.Length != a.Length)
return false;
int ndx = a.IndexOf(b[0]);
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
if (ndx == -1) return false;
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];
Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );
if (b[i] != rotatedA)
{
isRotation = false;
// break; uncomment this when you remove the Console.WriteLine
}
}
return isRotation;
}
Output:
A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False
A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True
A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True
A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False
A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False
[EDIT: 2010-04-12]
piotr noticed the flaw in my code above. It errors when the first character in the string occurs twice or more. For example, stackoverflow tested against owstackoverflow resulted in false, when it should be true.
Thanks piotr for spotting the error.
Now, here's the corrected code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace TestRotate
{
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", "tackoverflwos"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));
Console.ReadLine();
}
public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);
if (b.Length != a.Length)
return false;
if (a.IndexOf(b[0]) == -1 )
return false;
foreach (int ndx in IndexList(a, b[0]))
{
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];
Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);
if (b[i] != rotatedA)
{
isRotation = false;
break;
}
}
if (isRotation)
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 TestRotate
Here's the output:
A: stackoverflow B: ztackoverflow
Rotation : False
A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True
A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True
A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False
A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False
A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True
Here's the lambda approach:
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<string> 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
Here's the lambda approach 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
Whoa, whoa... why is everyone so thrilled with an O(n^2) answer? I'm positive that we can do better here. THE answer above includes an O(n) operation in an O(n) loop (the substring/indexOf call). Even with a more efficient search algorithm; say Boyer-Moore or KMP, the worst-case is still O(n^2) with duplicates.
A O(n) randomized answer is straightforward; take a hash (like a Rabin fingerprint) that supports an O(1) sliding window; hash string 1, then hash string 2, and proceed to move the window for hash 1 around the string and see if the hash functions collide.
If we imagine the worst case being something like "scanning two strands of DNA", then the probability of collisions goes up, and this probably degenerates to something like O(n^(1+e)) or something (just guessing here).
Finally, there's a deterministic O(nlogn) solution that has a very big constant outside. Basically, the idea is to take a convolution of the two strings. The max value of the convolution will be the rotation difference (if they are rotated); an O(n) check confirms. The nice thing is that if there are two equal max values, then they are both also valid solutions. You can do the convolution with two FFT's and a dot product, and an iFFT, so nlogn + nlogn + n + nlogn + n == O(nlogn).
Since you can't pad with zeroes, and you can't guarantee that the strings are of 2^n length, the FFTs won't be the fast ones; they'll be the slow ones, still O(nlogn) but a much bigger constant than the CT algorithm.
All that said, I'm absolutely, 100% positive that there is a deterministic O(n) solution here, but darned if I can find it.
A pure Java answer (sans null checks)
private boolean isRotation(String s1,String s2){
if(s1.length() != s2.length()) return false;
for(int i=0; i < s1.length()-1; i++){
s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
//--or-- s1 = s1.substring(1) + s1.charAt(0)
if(s1.equals(s2)) return true;
}
return false;
}
Fist, make sure the 2 strings have the same length. Then in C, you can do this with a simple pointer iteration.
int is_rotation(char* s1, char* s2)
{
char *tmp1;
char *tmp2;
char *ref2;
assert(s1 && s2);
if ((s1 == s2) || (strcmp(s1, s2) == 0))
return (1);
if (strlen(s1) != strlen(s2))
return (0);
while (*s2)
{
tmp1 = s1;
if ((ref2 = strchr(s2, *s1)) == NULL)
return (0);
tmp2 = ref2;
while (*tmp1 && (*tmp1 == *tmp2))
{
++tmp1;
++tmp2;
if (*tmp2 == '\0')
tmp2 = s2;
}
if (*tmp1 == '\0')
return (1);
else
++s2;
}
return (0);
}
Source: Stackoverflow.com