Question d'entrevue: vérifiez si une chaîne est une rotation de l'autre chaîne [fermé]

Une meilleure réponse serait sûrement: "Eh bien, je demanderais à la communauté stackoverflow et aurais probablement au moins 4 très bonnes réponses dans les 5 minutes". Les cerveaux sont bons et tous, mais j'accorderais une valeur plus élevée à quelqu'un qui sait travailler avec les autres pour obtenir une solution.

Un autre exemple python (basé sur la réponse):

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

Comme d'autres ont soumis une solution quadratique de complexité temporelle dans le pire des cas, j'en ajouterais une solution linéaire (basée sur la algorithme 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;
}

Exemple de Travail

EDIT: la réponse acceptée est clairement plus élégante et efficace que celle-ci, si vous la repérez. J'ai laissé cette réponse comme ce que je ferais si je n'avais pas pensé à doubler la chaîne d'origine.

Je le forcerais brutalement. Vérifiez d'abord la longueur, puis essayez tous les décalages de rotation possibles. Si aucun d'entre eux ne fonctionne, return false - si l'un d'entre eux le fait, return true immédiatement.

Il N'y a pas de besoin particulier de concaténer - il suffit d'utiliser des pointeurs (C) ou des index (Java) et de marcher les deux, un dans chaque chaîne-commençant au début d'une chaîne et le décalage de rotation candidat actuel dans la seconde chaîne, et enveloppant si nécessaire. Vérifiez l'égalité des caractères à chaque point de la chaîne. Si vous arrivez à la fin de la première chaîne, vous avez terminé.

Il serait probablement aussi facile de concaténer-bien que probablement moins efficace, au moins en Java.

En voici un qui utilise regex juste pour le plaisir:

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

Vous pouvez le rendre un peu plus simple si vous pouvez utiliser un caractère de délimiteur spécial garanti de ne pas être dans les deux chaînes.

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

Vous pouvez également utiliser lookbehind avec répétition finie à la place:

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

Whoa, whoa... pourquoi tout le monde est-il si ravi d'une réponse O(n^2)? Je suis certain que nous pouvons faire mieux ici. La réponse ci-dessus inclut une opération O(n) dans une boucle O(n) (l'appel substring/indexOf). Même avec un algorithme de recherche plus efficace; disons Boyer-Moore ou KMP, le pire des cas est toujours O(n^2) avec des doublons.

Une réponse aléatoire O(n) est simple; prenez un hachage (comme une empreinte Rabin) qui prend en charge une fenêtre coulissante O(1); chaîne de hachage 1, puis chaîne de hachage 2, et passez à déplacer la fenêtre de hachage 1 autour de la chaîne et voyez si les fonctions de hachage entrent en collision.

Si nous imaginons que le pire des cas est quelque chose comme "scanner deux brins D'ADN", alors la probabilité de collisions augmente, et cela dégénère probablement en quelque chose comme {[8] } ou quelque chose (juste deviner ici).

Enfin, il y a une solution déterministe O(nlogn) qui a une très grande constante à l'extérieur. Fondamentalement, l'idée est de prendre une convolution des deux chaînes. Max la valeur de la convolution sera la différence de rotation (si elles sont tournées); une vérification O(n) confirme. La bonne chose est que s'il y a deux valeurs maximales égales, alors elles sont toutes deux des solutions valides. Vous pouvez faire la convolution avec deux FFT et un produit dot, et un iFFT, donc nlogn + nlogn + n + nlogn + n == O(nlogn).

Puisque vous ne pouvez pas pad avec des zéros, et vous ne pouvez pas garantir que les chaînes sont de longueur 2^n, Les FFTs ne seront pas les rapides; ils seront les lents, toujours {[9] } mais une constante beaucoup plus grande que le CT de l'algorithme.

Tout cela dit, je suis absolument, 100% positif qu'il y a une solution déterministe O(n) ici, mais sacrément si je peux le trouver.

Poing, assurez-vous que les 2 cordes ont la même longueur. Ensuite, en C, vous pouvez le faire avec une simple itération de pointeur.

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

Voici un O(n) et en place alghoritm. Il utilise l'opérateur < pour les éléments des chaînes. Ce n'est pas le mien bien sûr. Je l'ai pris de ici (le site est en polonais. Je suis tombé dessus une fois dans le passé et je ne pouvais pas trouver quelque chose comme ça maintenant en anglais, alors je montre ce que j'ai :)).

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

Je suppose que c'est mieux de le faire dans Java:

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

En Perl je ferais:

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

Ou encore mieux en utilisant la fonction index au lieu de la regex:

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

Je ne sais pas si c'est la méthode la plus efficace, mais elle pourrait être relativement intéressante: la transformation Burrows-Wheeler. Selon L'article WP, toutes les rotations de l'entrée donnent la même sortie. Pour des applications telles que la compression, cela n'est pas souhaitable, donc la rotation d'origine est indiquée (par exemple par un index; voir l'article). Mais pour une simple comparaison indépendante de la rotation, cela semble idéal. Bien sûr, ce n'est pas nécessairement idéalement efficace!

Prenez chaque caractère comme une amplitude et effectuez une transformée de Fourier discrète sur eux. Si elles ne diffèrent que par la rotation, les spectres de fréquence seront les mêmes à l'intérieur de l'erreur d'arrondi. Bien sûr, cela est inefficace sauf si la longueur est une puissance de 2 donc vous pouvez faire un FFT : -)

Personne n'a encore proposé une approche modulo, alors en voici une:

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

Sortie:

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

[MODIFIER: 2010-04-12]

Piotr a remarqué la faille dans mon code ci-dessus. Il erreur lorsque le premier caractère de la chaîne se produit deux fois ou plus. Par exemple, stackoverflow testé contre owstackoverflow a abouti à false, quand il devrait être vrai.

Merci piotr pour avoir repéré l'erreur.

Maintenant, voici le code corrigé:

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

Voici le sortie:

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

Voici l'approche 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

Voici la sortie de l'approche 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

Comme personne n'a donné de solution c++. ici il IL:

bool isRotation(string s1,string s2) {

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

L'astuce de rotation simple du pointeur D'Opera fonctionne, mais elle est extrêmement inefficace dans le pire des cas en temps d'exécution. Imaginez simplement une chaîne avec de nombreuses longues séries répétitives de caractères, c'est-à-dire:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

La "boucle jusqu'à ce qu'il y ait une discordance, puis incrémenter par un et essayer à nouveau" est une approche horrible, informatique.

Pour prouver que vous pouvez faire le approche de concaténation en C Simple Sans trop d'effort, voici ma 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);
}

Ceci est linéaire dans le temps d'exécution, au détriment de L'utilisation de la mémoire O(n) en surcharge.

(notez que l'implémentation de strstr() est spécifique à la plate-forme, mais si elle est particulièrement cérébrale, elle peut toujours être remplacée par une alternative plus rapide telle que l'algorithme de Boyer-Moore)

C#:

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

J'aime la réponse qui vérifie si s2 est une sous-chaîne de S1 concaténée avec s1.

Je voulais ajouter une optimisation qui ne perd pas son élégance.

Au lieu de concaténer les chaînes, vous pouvez utiliser une vue de jointure (Je ne sais pas pour un autre langage, mais pour C++ Boost.Gamme fournir ce genre de vues).

Comme la vérification si une chaîne est une sous-chaîne d'une autre a une complexité moyenne linéaire (la complexité du pire des cas est quadratique), cette optimisation devrait améliorer la vitesse d'un facteur 2 en moyenne.

Une réponse Java pure (contrôles sans 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;
}

Et maintenant pour quelque chose de complètement différent.

Si vous voulez une réponse très rapide dans un contexte contraint lorsque les chaînes sontPas rotation les unes des autres

• calculez une somme de contrôle basée sur des caractères (comme xoring tous les caractères) sur les deux chaînes. Si les signatures diffèrent, les chaînes ne sont pas des rotations les unes des autres.

D'Accord, il peut échouer, mais c'est très fast-à-dire si les chaînes ne correspondent pas et si elles correspondent, vous pouvez toujours utiliser un autre algorithme, comme concaténation de chaîne à vérifier.

Un Autre Rubis solution basée sur l' réponse:

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

Il est très facile d'écrire en PHP en utilisant les fonctions strlen et strpos:

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

Je ne sais pas ce que strpos utilise en interne, mais si il utilise KMP, ce sera linéaire dans le temps.

Inverse une des chaînes. Prenez la FFT des deux (en les traitant comme de simples séquences d'entiers). Multipliez les résultats ensemble point par point. Transformer en arrière en utilisant FFT inverse. Le résultat aura un seul pic si les chaînes sont des rotations les unes des autres-la position du pic indiquera combien elles sont tournées les unes par rapport aux autres.

Pourquoi pas quelque chose comme ça?

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

Bien sûr, vous pouvez écrire votre propre fonction IndexOf (); Je ne suis pas sûr si. net utilise une manière naïve ou plus rapide.

Naïf:

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

Plus Rapide:

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: je pourrais avoir quelques problèmes décalés; Je n'ai pas envie de vérifier. ;)

Je le ferais dans 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;
}

Joignez string1 avec string2 et utilisez l'algorithme KMP pour vérifier si string2 est présent dans la chaîne nouvellement formée. Parce que la complexité temporelle de KMP est inférieure à substr.