Comment déterminer efficacement si deux chaînes sont des rotations l'une de l'autre ?

Vérifier la rotation des chaînes : une solution efficace

Lors d'un entretien pour un poste de développeur de logiciels, un candidat s'est vu poser un défi : déterminer si deux les chaînes sont des versions pivotées les unes des autres. Plus précisément, étant donné « s1 » et « s2 », la tâche consistait à vérifier si « s1 » est une version modifiée de « s2 » en faisant pivoter ses caractères.

L'approche de l'intervieweur

La réponse du candidat consistait à trouver le préfixe le plus long dans « s2 » qui correspondait à une sous-chaîne dans « s1 », qui représenterait le point de rotation. En divisant « s2 » à ce stade en « s2a » et « s2b », la concaténation de « s2a » et « s2b » pourrait être comparée à « s1 » pour l'égalité.

Une solution plus simple

Cependant, l'intervieweur a suggéré une approche plus directe : s'assurer que "s1" et "s2" ont la même longueur, puis tester si "s2" est une sous-chaîne de "s1" concaténée avec elle-même. Cette méthode exploite le fait qu'une chaîne pivotée sera toujours une sous-chaîne de la chaîne d'origine lorsqu'elle sera concaténée avec elle.

Implémentation Java

En Java, une implémentation simple de cette solution pourrait ressembler à :

<code class="java">boolean isRotation(String s1, String s2) {
    return (s1.length() == s2.length()) && ((s1 + s1).indexOf(s2) != -1);
}</code>

Analyse d'efficacité

La complexité temporelle de cette solution est O(n), où n est la longueur des chaînes, puisqu'elle implique une concaténation de chaîne unique et une recherche de sous-chaîne sur le résultat combiné. La complexité spatiale est également O(n), en raison de l'espace requis pour la chaîne concaténée.

En fournissant une méthode simple et efficace pour vérifier la rotation des chaînes, cette approche alternative répond à la demande de simplicité et d'efficacité de l'intervieweur. détecte les versions pivotées des chaînes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!