Pytanie o wywiad: sprawdź, czy jeden ciąg jest rotacją drugiego łańcucha [zamknięty]

Z pewnością lepszą odpowiedzią byłoby: "cóż, zapytałbym społeczność stackoverflow i prawdopodobnie otrzymałby co najmniej 4 naprawdę dobre odpowiedzi w ciągu 5 minut". Mózg jest dobry i w ogóle, ale chciałbym umieścić większą wartość na kogoś, kto wie, jak pracować z innymi, aby znaleźć rozwiązanie.

Kolejny przykład Pythona (oparty na odpowiedzi):

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

Ponieważ inni przedstawili rozwiązanie kwadratowej złożoności czasu, dodałbym liniową (opartą na algorytm 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;
}

Przykład roboczy

EDIT: przyjęta odpowiedź jest wyraźnie bardziej elegancka i skuteczna niż ta, jeśli ją zauważysz. Zostawiłam tę odpowiedź jako to, co bym zrobiła, gdybym nie pomyślała o podwojeniu oryginalnego ciągu.

Po prostu brutalnie na siłę. Najpierw sprawdź długość, a następnie spróbuj każdego możliwego przesunięcia obrotu. Jeśli żaden z nich nie zadziała, zwróć false - jeśli któryś z nich zadziała, natychmiast zwróć true.

Nie ma szczególnej potrzeby łączenia-wystarczy użyć pointerów (C) lub indeksów (Java) i przejść obie, po jednym w każdym łańcuchu-począwszy od początku jednego łańcucha i aktualnego przesunięcia rotacji kandydata w drugim łańcuchu, a w razie potrzeby owijania. Sprawdź równość znaków w każdym punkcie łańcucha. Jeśli dojdziesz do końca pierwszego Sznurka, jesteś skończony.

Byłoby to prawdopodobnie równie łatwe do konkatenacji-choć prawdopodobnie mniej wydajne, przynajmniej w Javie.

Oto jeden z użyciem regex tylko dla Zabawy:

boolean isRotation(String s1, String s2) {
   return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}

Możesz to nieco uprościć, jeśli możesz użyć specjalnego znaku ogranicznika gwarantującego, że nie będzie w żadnym z łańcuchów.

boolean isRotation(String s1, String s2) {
   // neither string can contain "="
   return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}

Możesz również użyć lookbehind z skończonym powtórzeniem:

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

Whoa, whoa... dlaczego wszyscy są tak podekscytowani odpowiedzią O(n^2)? Jestem pewien, że możemy zrobić więcej tutaj. Powyższa odpowiedź zawiera operację O(n) W pętli O(n) (wywołanie substring/indexOf). Nawet przy bardziej wydajnym algorytmie wyszukiwania; powiedzmy Boyer-Moore lub KMP, najgorszy przypadek jest nadal {[0] } z duplikatami.

A O(n) randomizowana odpowiedź jest prosta; weź hash (jak odcisk palca rabina), który obsługuje przesuwane okno O(1); hash string 1, następnie hash string 2 i przejdź do przesunięcia okna skrótu 1 wokół ciągu znaków i sprawdź, czy funkcje skrótu kolidują.

Jeśli wyobrażamy sobie, że najgorszym przypadkiem jest coś w rodzaju "skanowania dwóch nici DNA", wtedy prawdopodobieństwo kolizji wzrasta, a to prawdopodobnie degeneruje się do czegoś w rodzaju O(n^(1+e)) lub czegoś takiego (tylko zgadywanie tutaj).

Ponieważ nie można pad z zerami, i nie można zagwarantować, że ciągi są 2^N długości, FFTs nie będą te szybkie, będą te powolne, nadal O(nlogn) ale znacznie większa stała niż algorytm CT.

Pięść, upewnij się, że 2 struny mają tę samą długość. Następnie w C możesz to zrobić za pomocą prostej iteracji wskaźnika.

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

Tutaj jest O(n) i na miejscu alghoritm. Używa operatora < dla elementów łańcuchów. Oczywiście nie jest mój. Ja wziąłem to z tutaj (strona jest w języku polskim. Natknęłam się na nią kiedyś i nie mogłam znaleźć czegoś takiego teraz po angielsku, więc pokazuję co mam :)).

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

Chyba lepiej to zrobić w Java:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}

W Perlu zrobiłbym:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}

Lub jeszcze lepiej używając funkcjiindex zamiast regex:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}

Nie wiem, czy jest to najskuteczniejsza metoda, ale może być względnie interesująca : transformata Burrowsa-Wheelera . Zgodnie z artykułem WP, wszystkie obroty wejścia dają to samo wyjście. W przypadku aplikacji takich jak kompresja nie jest to pożądane, więc oryginalny obrót jest wskazywany (np. przez indeks; patrz artykuł). Ale dla prostego, niezależnego od obrotów porównania brzmi to idealnie. Oczywiście nie koniecznie jest idealnie wydajny!

Weź każdy znak jako amplitudę i wykonaj na nich dyskretną transformację Fouriera. Jeśli różnią się tylko obrotem, widmo częstotliwości będzie takie samo jak w przypadku błędu zaokrąglania. Oczywiście jest to nieefektywne, chyba że długość jest mocą 2, więc można zrobić FFT: -)

Nikt jeszcze nie zaproponował podejścia modulo, więc oto jeden:

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

Wyjście:

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

[edytuj: 2010-04-12]

Piotr zauważył wadę w powyższym kodzie. Błąd występuje, gdy pierwszy znak w łańcuchu występuje dwa lub więcej razy. Na przykład, stackoverflow testowane pod kątem owstackoverflow zaowocowało false, kiedy powinno być prawdziwe.

Dzięki piotr za Zauważenie błędu.

Oto poprawiony kod:

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

Oto wyjście:

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

Oto podejście lambda:

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

Oto wyjście podejścia lambda:

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

Ponieważ nikt nie podał rozwiązania C++. tutaj jest to:

bool isRotation(string s1,string s2) {

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

Prosty trik rotacji wskaźnika w Operze działa, ale w najgorszym przypadku jest niezwykle nieefektywny. Po prostu wyobraź sobie ciąg znaków z wieloma długimi powtarzającymi się ciągami znaków, tj.:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

"pętla dopóki nie będzie niedopasowania, następnie zwiększenie o jeden i spróbuj ponownie" jest okropnym podejściem, obliczeniowo.

Aby udowodnić, że można zrobić podejście do konkatenacji w prostym C bez zbytniego wysiłku, oto moje rozwiązanie:

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

To jest liniowe w czasie pracy, kosztem O(n) wykorzystania pamięci w napowietrznych.

(zauważ, że implementacja strstr () jest specyficzna dla platformy, ale jeśli jest szczególnie Martwa dla mózgu, zawsze może być zastąpiona szybszą alternatywą, taką jak algorytm Boyera-Moore ' a)

C#:

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

Podoba mi się odpowiedź, która sprawdza, czy S2 jest podłańcuchem S1 połączonym z s1.

Chciałem dodać optymalizację, która nie traci elegancji.

Zamiast łączenia łańcuchów możesz użyć widoku join (Nie wiem Dla innego języka, ale dla C++ Boost.Zasięg takich widoków).

Ponieważ sprawdzanie, czy łańcuch jest podłańcuchem innego ma średnią złożoność liniową( w najgorszym przypadku złożoność jest kwadratowa), optymalizacja ta powinna poprawić prędkość o współczynnik średnio 2.

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

A teraz coś zupełnie innego.

Jeśli chcesz naprawdę szybką odpowiedź w jakimś ograniczonym kontekście, gdy ciągi są a nie obracają się nawzajem

• Oblicz sumę kontrolną opartą na znakach (np. xoring wszystkich znaków) na obu łańcuchach. Jeśli sygnatury różnią się, ciągi nie są rotacjami siebie nawzajem.

Zgadzam się, to może się nie udać, ale to jest Bardzo szybko powiedzieć, jeśli ciągi nie pasują i jeśli pasują nadal można użyć innego algorytmu, takiego jak string concatenation to check.

Kolejne rozwiązanie Ruby oparte na na odpowiedź:

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

Bardzo łatwo jest pisać w PHP za pomocą funkcji strlen i strpos:

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

Nie wiem, co strpos używa wewnętrznie, ale jeśli używa KMP będzie to liniowe w czasie.

Odwróć jeden ze sznurków. Weźmy FFT obu (traktując je jako proste sekwencje liczb całkowitych). Pomnożyć wyniki razem punktowo. Transformacja z powrotem za pomocą odwrotnego FFT. Wynik będzie miał pojedynczy pik, jeśli ciągi są rotacjami siebie - położenie piku będzie wskazywać przez to, jak bardzo są one obracane względem siebie.

Dlaczego nie coś takiego?

//is q a rotation of p?
bool isRotation(string p, string q) {
    string table = q + q;    
    return table.IndexOf(p) != -1;
}

Oczywiście możesz napisać własną funkcję IndexOf (); nie jestem pewien, czy. NET używa naiwnej czy szybszej metody.

Naiwny:

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

Szybciej:

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: mogę mieć pewne problemy off-by-one; nie mam ochoty sprawdzać. ;)

Zrobiłbym to w 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;
}

Połącz string1 z string2i użyj algorytmu KMP, aby sprawdzić, czy string2 jest obecny w nowo utworzonym łańcuchu. Ponieważ złożoność czasowa KMP jest mniejsza niż substr.