Моего друга задали следующий вопрос сегодня на интервью относительно должности разработчика программного обеспечения:
Учитывая два представляют в виде строки s1
и s2
как Вы проверите если s1
повернутая версия s2
?
Пример:
Если s1 = "stackoverflow"
затем следующее является некоторыми своими повернутыми версиями:
"tackoverflows"
"ackoverflowst"
"overflowstack"
где как "stackoverflwo"
не повернутая версия.
Ответ, который он дал, был:
Взять
s2
и найдите самый длинный префикс, который является sub строкойs1
, это даст Вам точку вращения. После того как Вы находите ту точку, повреждениеs2
в той точке для полученияs2a
иs2b
, затем просто проверьте еслиconcatenate(s2a,s2b) == s1
Это похоже на хорошее решение меня и моего друга. Но интервьюер думал иначе. Он попросил простое решение. Помогите мне путем сообщения, как Вы выполнили бы в этом Java/C/C++
?
Заранее спасибо.
Сначала убедитесь, что s1
и s2
одинаковой длины. Затем проверьте, является ли s2
подстрокой s1
, конкатенированной с s1
:
algorithm checkRotation(string s1, string s2)
if( len(s1) != len(s2))
return false
if( substring(s2,concat(s1,s1))
return true
return false
end
На Java:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
Другое решение Ruby, основанное на ответе :
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
Поскольку другие представили квадратичное решение для наихудшего случая временной сложности, я бы добавил линейное (на основе алгоритма KMP ):
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;
}
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;
}
Конечно, лучшим ответом было бы: «Хорошо, я бы спросил сообщество stackoverflow и, вероятно, получил бы по крайней мере 4 действительно хороших ответа в течение 5 минут». Мозги хороши и все такое, но я бы больше ценил того, кто знает, как работать с другими, чтобы найти решение.
РЕДАКТИРОВАТЬ: принятый ответ явно более элегантен и эффективен, чем этот, если вы его заметили. Я оставил этот ответ таким же, как и сделал бы, если бы не подумал об удвоении исходной строки.
Я бы просто взломал его. Сначала проверьте длину, а затем попробуйте все возможные смещения поворота. Если ни один из них не работает, верните false - если какой-либо из них - немедленно верните true.
Нет особой необходимости в объединении - просто используйте указатели (C) или индексы (Java) и пройдите по обоим направлениям, по одному в каждой строке - начиная с начала одной строки и текущего смещения вращения кандидата во второй строке, и упаковка при необходимости. Проверьте равенство символов в каждой точке строки. Если вы дойдете до конца первой строки, все готово.
Вероятно, это было бы так же легко объединить - хотя, вероятно, менее эффективно, по крайней мере, в Java.
Во-первых, убедитесь, что две строки имеют одинаковую длину. Затем в C вы можете сделать это с помощью простой итерации указателя.
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);
}
Подход по модулю пока никто не предлагал, поэтому вот один:
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;
}
Результат:
{{1 }}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]
пиотр заметил ошибку в моем приведенном выше коде. Это ошибка, когда первый символ в строке встречается дважды или более. Например, stackoverflow
, протестированный против owstackoverflow
, привел к ложному, тогда как он должен быть истинным.
Спасибо piotr за обнаружение ошибки.
Вот исправленный код:
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
Вот результат:
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
Вот лямбда-подход:
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
Вот результат лямбда-подхода:
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
Думаю, лучше сделать это в Java
:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
В Perl я бы сделал:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}
или даже лучше, используя индекс Функция вместо регулярного выражения:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
Простой трюк Opera с вращением указателя работает, но он крайне неэффективен в худшем случае по времени работы. Представьте себе строку с большим количеством длинных повторяющихся символов, например:
S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2
S2 = HELLOHELLOHELLO2HELLOHELLOHELLOHELLO1
Зацикливание до несовпадения, затем увеличение на единицу и повторная попытка - ужасный подход с вычислительной точки зрения.
Чтобы доказать, что подход конкатенации можно реализовать на обычном C без особых усилий, вот мое решение:
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);
}
Это линейно по времени выполнения, за счет O(n) использования памяти в накладных расходах.
(Обратите внимание, что реализация strstr() зависит от платформы, но если вы особенно тупы, то всегда можете заменить ее более быстрой альтернативой, например, алгоритмом Бойера-Мура)
.Другой пример Python (на основе ответа):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
Здесь используется регулярное выражение для развлечения:
boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
Вы можете сделать это немного проще, если можете использовать специальный символ-разделитель, который гарантированно не будет ни в одной из строк.
boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
Вместо этого вы также можете использовать ретроспективный просмотр с конечным повторением:
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
Не уверен, что это наиболее эффективный метод, но он может быть относительно интересным : преобразование Барроуза-Уиллера . Согласно статье WP, все вращения входа дают одинаковый результат. Для таких приложений, как сжатие, это нежелательно, поэтому указывается исходное вращение (например, индексом; см. Статью). Но для простого сравнения, независимого от вращения, это звучит идеально. Конечно, это не обязательно идеально!
C #:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
Эй, эй ... почему все так взволнованы ответом O (n ^ 2)
? Я уверен, что здесь мы можем добиться большего успеха. ПРИВЕДЕННЫЙ выше ответ включает операцию O (n)
в цикле O (n)
(вызов substring / indexOf). Даже с более эффективным алгоритмом поиска; скажем, Boyer-Moore
или KMP
, наихудший случай все еще O (n ^ 2)
с дубликатами.
O (n)
рандомизированный ответ прост; возьмите хеш (например, отпечаток Рабина), который поддерживает скользящее окно O (1)
; хеш-строка 1, затем хеш-строка 2, и продолжаем перемещать окно для хеш-функции 1 вокруг строки и смотреть, не конфликтуют ли хеш-функции.
Если представить наихудший случай как что-то вроде «сканирования двух нитей ДНК», то вероятность столкновений возрастает, и это, вероятно, вырождается к чему-то вроде O (n ^ (1 + e))
или что-то в этом роде (здесь просто догадываюсь).
Наконец, есть детерминированное решение O (nlogn)
, которое имеет очень большую константу снаружи. По сути, идея состоит в том, чтобы сделать свертку двух струн. Максимальное значение свертки будет разницей поворота (если они повернуты); проверка O (n)
подтверждает. Приятно то, что если есть два равных максимальных значения, они оба также являются допустимыми решениями. Вы можете выполнить свертку с двумя БПФ, скалярным произведением и iFFT, так что nlogn + nlogn + n + nlogn + n == O (nlogn)
.
Поскольку вы не можете заполнять нулями и не можете гарантировать, что строки имеют длину 2 ^ n, БПФ не будет быстрым; они будут медленными, все еще O (nlogn)
, но с гораздо большей константой, чем алгоритм CT.
С учетом всего сказанного, я абсолютно, на 100% уверен, что здесь есть детерминированное O (n)
решение, но черт возьми, если я смогу его найти.
Почему бы не сделать что-то подобное?
//is q a rotation of p?
bool isRotation(string p, string q) {
string table = q + q;
return table.IndexOf(p) != -1;
}
Конечно, вы могли бы написать свою собственную функцию IndexOf (); Я не уверен, использует ли .NET наивный способ или более быстрый способ.
Наивный:
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;
}
Быстрее:
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;
}
Редактировать: У меня могут быть отдельные проблемы; не хочется проверять. ;)
Поскольку никто не дал решения на C ++. вот оно:
bool isRotation(string s1,string s2) {
string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
Мне нравится ответ, который проверяет, является ли s2 подстрокой s1, объединенной с s1.
Я хотел добавить оптимизацию, которая не теряет своей элегантности.
Вместо объединения строк вы можете использовать представление соединения (я не знаю другого языка, но для C ++ Boost.Range предоставляет такие представления).
Поскольку проверка того, является ли строка подстрокой другой, имеет линейную среднюю сложность (сложность в худшем случае квадратичная), эта оптимизация должна повысить скорость в среднем в 2 раза.
Вот O (n)
и вместо alghoritm. Он использует оператор <
для элементов строк. Это конечно не моё. Я взял его с здесь (Сайт на полировке. Я наткнулся на него однажды в прошлом, и я не мог найти что-то подобное сейчас на английском языке, поэтому я показываю то, что у меня есть :)).
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;
}
Чистый ответ Java (без проверок на null)
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;
}
Я бы сделал это в Perl :
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
Очень легко написать на PHP, используя функции strlen
и strpos
:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
Я не знать, что strpos
использует для внутренних целей, но если он использует KMP , это будет линейно во времени.
А теперь о другом.
Если вы хотите получить действительно быстрый ответ в некотором ограниченном контексте, когда строки , а не , вращение друг друга
Согласен, это может привести к сбою, но очень быстро сказать, если строки не совпадают, и если они совпадают, вы все равно можете использовать другой алгоритм, например конкатенацию строк, для проверки.