Question d'entretien : Vérifiez si une corde est une rotation d'une autre corde.

Question

Un de mes amis s'est vu poser la question suivante aujourd'hui lors d'un entretien pour le poste de développeur de logiciels :

Étant donné deux chaînes de caractères s1 et s2 comment allez-vous vérifier si s1 est un tourné version de s2 ?

Exemple :

Si s1 = "stackoverflow" alors voici quelques-unes de ses versions tournées :

"tackoverflows"
"ackoverflowst"
"overflowstack"

où comme "stackoverflwo" est pas une version pivotée.

La réponse qu'il a donnée est la suivante :

Prenez s2 et trouver le plus long préfixe qui est une sous-chaîne de caractères de s1 qui vous donnera le point de rotation. Une fois que tu as trouvé ce point, casse s2 à ce moment-là pour obtenir s2a et s2b alors il suffit de vérifier si concatenate(s2a,s2b) == s1

Cela semble être une bonne solution pour moi et mon ami. Mais l'interviewer pensait autrement. Il a demandé une solution plus simple. Veuillez m'aider en me disant comment vous feriez cela en Java/C/C++ ?

Merci d'avance.

Answer 1

Assurez-vous d'abord s1 et s2 sont de la même longueur. Vérifiez ensuite si s2 est une sous-chaîne de s1 concaténée avec 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

En Java :

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

Answer 2

Une meilleure réponse serait sans doute : "Je demanderais à la communauté stackoverflow et j'obtiendrais probablement au moins quatre bonnes réponses en cinq minutes". Les cerveaux, c'est bien et tout, mais j'accorderais plus de valeur à quelqu'un qui sait travailler avec d'autres pour trouver une solution.

Answer 3

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

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

Answer 4

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

exemple de travail

Answer 5

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 j'aurais fait si je n'avais pas pensé à doubler la chaîne originale.

---

Je le ferais par la force brute. Vérifiez d'abord la longueur, puis essayez tous les décalages de rotation possibles. Si aucun d'entre eux ne fonctionne, retournez false - si l'un d'entre eux fonctionne, retournez true immédiatement.

Il n'y a pas de besoin particulier de concaténation - il suffit d'utiliser des pointeurs (C) ou des index (Java) et de parcourir les deux, un dans chaque chaîne - en commençant par le début d'une chaîne et le décalage de rotation du candidat actuel dans la deuxième chaîne, et en 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, du moins en Java.