Vérifier si une chaîne est la rotation de l'autre, SANS la concaténation

Une solution simple est de la concaténation et de vérifier si l'autre est une sous-chaîne de la concaténation de version.

Je suppose que vous voulez dire concaténer la première chaîne avec lui-même, puis vérifier si l'autre est une sous-chaîne de la concaténation.

Qui va travailler, et en fait peut être fait sans la concaténation. Juste à l'utiliser tout algorithme de recherche de chaîne de caractères à la recherche de la deuxième chaîne dans le premier, et lorsque vous atteignez la fin, la boucle de retour pour le début.

Par exemple, à l'aide de Boyer-Moore l'ensemble de l'algorithme O(n).

OriginalL'auteur BlueRaja - Danny Pflughoeft

On peut calculer la lexicographiquement minimale de la chaîne de rotation de chaque chaîne, puis de tester s'ils sont égaux.

Le calcul du mouvement de rotation minimal est de O(n).

Ce serait bien si vous aviez beaucoup de cordes à l'essai, comme le mouvement de rotation minimal pourrait être appliqué comme une étape de prétraitement, et puis vous pouvez utiliser une table de hachage pour stocker la rotation de chaînes.

OriginalL'auteur Peter de Rivaz

Une solution très simple est de faire tourner l'un des mots n fois, où n est la longueur du mot. Pour chacune de ces rotations, vérifier pour voir si le résultat est le même que l'autre mot.

OriginalL'auteur David

Solution Simple en Java. Pas besoin de l'itération ou la concaténation.

private static boolean isSubString(String first, String second){
        int firstIndex = second.indexOf(first.charAt(0));
        if(first.length() == second.length() && firstIndex > -1){

            if(first.equalsIgnoreCase(second))
                return true;

            int finalPos = second.length() - firstIndex ; 
            return second.charAt(0) == first.charAt(finalPos)
            && first.substring(finalPos).equals(second.subSequence(0, firstIndex));
        }
        return false;

    }

Cas de Test:

String first = "bottle";
String second = "tlebot";

Logique:

Prenez la première chaîne du premier caractère, trouver l'index de la deuxième chaîne. Soustraire la longueur de la deuxième avec l'indice trouvé, vérifiez si le premier caractère de la deuxième à 0 est la même que le caractère à la différence de la longueur de la deuxième et de l'indice et des sous-chaînes entre ces 2 personnages sont les mêmes.

OriginalL'auteur Nikola Despotoski

input1= "bonjour" 2="llohe" input3="lohel"(input3 est cas spécial)

si la longueur de l'entrée 1 & 2 ne sont pas un rendement de 0.Soit i et j deux indices pointant vers input1 et input2, respectivement, et initialiser le comte de input1.longueur. Avoir un indicateur appelé isRotated qui est à false

while(compteur != 0){

Lorsque le personnage est de 1 correspond à input2

1. incrémenter i & j
2. décrémenter le comte

Si le personnage ne correspondent

1. si isRotated = true(c'est à dire même après la rotation il y a incompatibilité), de sorte break;
2. d'autre Réinitialiser j à 0 comme il existe une incompatibilité. Par exemple:

Vous trouverez le code ci-dessous et laissez-moi savoir si il échoue pour une autre combinaison que je n'auriez pas pensé.

    public boolean isRotation(String input1, String input2) {
    boolean isRotated = false;
    int i = 0, j = 0, count = input1.length();

    if (input1.length() != input2.length())
        return false;

    while (count != 0) {

        if (i == input1.length() && !isRotated) {
            isRotated = true;
            i = 0;
        }

        if (input1.charAt(i) == input2.charAt(j)) {
            i++;
            j++;
            count--;
        }

        else {
            if (isRotated) {
                break;
            }
            if (i == input1.length() - 1 && !isRotated) {
                isRotated = true;
            }
            if (i < input1.length()) {
                j = 0;
                count = input1.length();

            }
            /* To handle the duplicates. This is the special case.
             * This occurs when input1 contains two duplicate elements placed side-by-side as "ll" in "hello" while 
             * they may not be side-by-side in input2 such as "lohel" but are still valid rotations. 
             Eg: "hello" "lohel"
            */
            if (input1.charAt(i) == input2.charAt(j)) {
                i--;
            }
            i++;
        }
    }
    if (count == 0)
        return true;
    return false;
}

public static void main(String[] args) {
    //TODO Auto-generated method stub
    System.out.println(new StringRotation().isRotation("harry potter",
            "terharry pot"));
    System.out.println(new StringRotation().isRotation("hello", "llohe"));
    System.out.println(new StringRotation().isRotation("hello", "lohell"));
    System.out.println(new StringRotation().isRotation("hello", "hello"));
    System.out.println(new StringRotation().isRotation("hello", "lohe"));
}

OriginalL'auteur user1556718

    String source = "avaraavar";
    String dest =   "ravaraava";

    System.out.println();
    if(source.length()!=dest.length())
        try {
            throw (new IOException());
        } catch (Exception e) {
            //TODO Auto-generated catch block
            e.printStackTrace();
        }

    int i = 0;
    int j = 0;
    int totalcount=0;
    while(true)
    {
        i=i%source.length();    
        if(source.charAt(i)==dest.charAt(j))
        {   
            System.out.println("i="+i+" , j = "+j);
            System.out.println(source.charAt(i)+"=="+dest.charAt(j));
            i++;
            j++;
            totalcount++;   
        }
        else
        {
            System.out.println("i="+i+" , j = "+j);
            System.out.println(source.charAt(i)+"!="+dest.charAt(j));
            i++;
            totalcount++;   
            j=0;
        }
        if(j==source.length())
        {
            System.out.println("Yes its a rotation");
            break;
        }
        if(totalcount >(2*source.length())-1)
        {
            System.out.println("No its a rotation");
            break;
        }
    }

OriginalL'auteur ukdaga