Интервью: проверьте, является ли одна строка вращением другой строки [закрыто]

Моему другу на собеседовании на должность разработчика программного обеспечения был задан следующий вопрос:

Учитывая две строки, s1и s2как вы будете проверять, s1является ли повернутая версия s2?

Пример:

Если s1 = "stackoverflow"затем следующие некоторые из его повернутых версий:

"tackoverflows"
"ackoverflowst"
"overflowstack"

где , как "stackoverflwo"это не повернутая версия.

Ответ, который он дал, был:

Возьмите s2и найдите самый длинный префикс, который является подстрокой 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);
}

Конечно, лучшим ответом было бы: «Ну, я бы попросил сообщество stackoverflow и, вероятно, получило бы как минимум 4 действительно хороших ответа в течение 5 минут». Мозги хороши и все такое, но я бы больше ценил того, кто знает, как работать с другими, чтобы найти решение.

Еще один пример с питоном (основанный на ответе):

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

Поскольку другие представили квадратичное решение для временной сложности в худшем случае, я бы добавил линейное решение (на основе алгоритма 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;
}

рабочий пример

РЕДАКТИРОВАТЬ: Принятый ответ явно более элегантный и эффективный, чем этот, если вы его заметили. Я оставил этот ответ как то, что сделал бы, если бы не думал удвоить исходную строку.

Я бы просто перебор. Сначала проверьте длину, а затем попробуйте все возможные смещения вращения. Если ни один из них не сработает, верните false - если любой из них сработает, немедленно верните true.

Нет особой необходимости объединять - просто используйте указатели (C) или индексы (Java) и идите вместе, по одному в каждой строке - начиная с начала одной строки и текущего смещения вращения кандидата во второй строке, и оборачивая при необходимости , Проверьте равенство символов в каждой точке строки. Если вы доберетесь до конца первой строки, все готово.

Вероятно, объединить его будет так же легко, хотя, возможно, и менее эффективно, по крайней мере в Java.

Вот один из них, использующий регулярное выражение просто для удовольствия:

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

Вы также можете использовать lookbehind с конечным повторением:

boolean isRotation(String s1, String s2) {
   return (s1 + s2).matches(
      String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
   );
}

Воу, воу ... почему все так взволнованы 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)проверка подтверждает. Приятно то, что если есть два равных максимальных значения, то оба они также являются допустимыми решениями. Вы можете сделать свертку с двумя FFT и точечным продуктом, и iFFT, так nlogn + nlogn + n + nlogn + n == O(nlogn).

Поскольку вы не можете заполнить нулями и не можете гарантировать, что строки имеют длину 2 ^ n, FFT не будут быстрыми; они будут медленными, все ещеO(nlogn) но с гораздо большей константой, чем алгоритм CT.

Все это говорит о том, что я абсолютно на 100% уверен, что здесь есть детерминистическое O(n)решение, но проклят, если смогу его найти.

Кулак, убедитесь, что 2 строки имеют одинаковую длину. Затем в 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);
}

Вот O(n)и на месте Алгоритм. Он использует <оператор для элементов строк. Это не мое, конечно. Я взял его отсюда (Сайт на польском языке. Я однажды наткнулся на него и не смог найти что-то подобное сейчас на английском, поэтому я покажу, что у меня есть :)).

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:

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

Не уверен, что это самый эффективный метод, но он может быть относительно интересным : преобразование Барроуза-Уилера . Согласно статье WP, все чередования входов дают одинаковый результат. Для таких приложений, как сжатие, это нежелательно, поэтому указывается исходное вращение (например, индексом; см. Статью). Но для простого независимого от вращения сравнения это звучит идеально. Конечно, это не обязательно идеально эффективно!

Возьмите каждый символ в качестве амплитуды и выполните дискретное преобразование Фурье для них. Если они отличаются только вращением, частотные спектры будут одинаковыми с точностью до погрешности округления. Конечно, это неэффективно, если длина не является степенью 2, поэтому вы можете сделать БПФ :-)

Никто еще не предложил подход по модулю, так что вот один:

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

Вывод:

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

[РЕДАКТИРОВАТЬ: 2010-04-12]

Петр заметил недостаток в моем коде выше. Это ошибки, когда первый символ в строке встречается дважды или более. Например, stackoverflowпроверка на owstackoverflowрезультат привела к ложному результату, когда оно должно быть истинным.

Спасибо, Петр, за обнаружение ошибки.

Теперь исправленный код:

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

Поскольку никто не дал решение C ++. вот это оно:

bool isRotation(string s1,string s2) {

  string temp = s1;
  temp += s1;
  return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}

Простой трюк поворота указателя в Opera работает, но он крайне неэффективен в худшем случае во время выполнения. Просто представьте строку со множеством длинных повторяющихся серий символов, а именно:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

«Цикл, пока не будет несоответствия, затем увеличьте его на единицу и попробуйте снова» - это ужасный подход в вычислительном отношении.

Чтобы доказать, что вы можете использовать подход конкатенации в простом 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 () зависит от платформы, но, если она не работает, ее всегда можно заменить более быстрой альтернативой, такой как алгоритм Бойера-Мура)

C #:

s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)

Мне нравится ответ THE, который проверяет, является ли s2 подстрокой s1, объединенной с s1.

Я хотел добавить оптимизацию, которая не теряет своей элегантности.

Вместо объединения строк вы можете использовать представление соединения (я не знаю для другого языка, но для C ++ Boost.Range предоставляют такие виды представлений).

Поскольку проверка того, является ли строка подстрокой другой, имеет линейную среднюю сложность (сложность наихудшего случая является квадратичной), эта оптимизация должна повысить скорость в среднем в 2 раза.

Чистый Java-ответ (без проверки нуля)

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

А сейчас нечто соверешнно другое.

Если вам нужен действительно быстрый ответ в ограниченном контексте, когда строки не вращаются друг относительно друга

• вычислить некоторую символьную контрольную сумму (например, ксерокса всех символов) для обеих строк Если подписи различаются, строки не являются вращениями друг друга.

Согласен, он может потерпеть неудачу, но очень быстро сказать, если строки не совпадают и если они совпадают, вы все равно можете использовать другой алгоритм, такой как конкатенация строк, для проверки.

Другое решение Руби на основе в ответ:

def rotation?(a, b); a.size == b.size and (b*2)[a]; end

Это очень легко написать на PHP, используя strlenи strposфункции:

function isRotation($string1, $string2) {
    return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}

Я не знаю, что strposиспользует внутренне, но если это использует KMP, это будет линейно во времени.

Переверните одну из строк. Возьмите БПФ обоих (рассматривая их как простые последовательности целых чисел). Умножьте результаты вместе по точкам. Преобразование обратно с использованием обратного БПФ. Результат будет иметь один пик, если струны являются вращениями друг друга - положение пика будет указывать на то, насколько они повернуты друг относительно друга.

Почему не как то так?

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

Редактировать: у меня могут быть некоторые личные проблемы; не хочется проверять ;)

Я бы сделал это в Perl :

sub isRotation { 
     return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1; 
}

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

Регистрация string1с string2и использовать алгоритм КМП для проверки string2присутствует во вновь сформированной строки. Потому что временная сложность КМП меньше, чем substr.