Leetcode — Différence de permutation entre deux chaînes

Il s'agit d'une question simple avec la signification suivante :

Étant donné deux chaînes s et t, chaque caractère de s apparaît au plus une fois et t est une permutation de s.

La différence de permutation entre s et t est définie comme la somme des différences absolues entre l'indice d'occurrence de chaque caractère dans s et l'indice de son occurrence dans t.

Renvoie la différence de permutation entre s et t.

Exemple 1 :

Entrée : s = "abc", t = "bac"

Sortie : 2

Explication :

Pour s = "abc" et t = "bac", la différence des permutations de s et t est égale à la somme de :

La différence absolue entre l'indice d'occurrence de "a" dans

s et l'indice d'occurrence de "a" dans t.

La différence absolue entre l'indice d'occurrence de "b" dans

s et l'indice d'occurrence de "b" dans t.

La différence absolue entre l'indice d'occurrence de "c" dans

s et l'indice d'occurrence de "c" dans t.

C'est-à-dire que la différence de permutation entre s et t est égale à |0 - 1| |1 - 0| |2 - 2|

Exemple 2 :

Entrée : s = "abcde", t = "edbac"

Sortie : 12

Explication : La différence de permutation entre s et t est égale à |0 - 3| |1 - 2| |2 - 4| |4 - 0|

Contraintes :

1 ≤ longueur s ≤ 100

Chaque caractère dans

s apparaît au plus une fois.

c'est une permutation de s.

Les

ne contiennent que des lettres anglaises minuscules.

La description du titre est longue, mais regarder un exemple permettra de mieux comprendre l'objectif du titre.

Selon la méthode de calcul de la différence de permutation, les étapes suivantes doivent être effectuées :

• Traversez la corde
• Récupérer les caractères en fonction de l'index
• Trouver l'index du caractère dans la deuxième chaîne
• Soustrayez le deuxième indice du premier ;
• Obtenez la valeur absolue de cette soustraction et accumulez tous les résultats en une seule sortie.

Convertissons maintenant cette idée en code Java :

class Solution {
    public int findPermutationDifference(String s, String t) {
        int output = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int j = t.indexOf(c);
            output += Math.abs(i - j);
        }
        return output;
    }
}

Durée d'exécution : 1 ms, plus rapide que 100 % des soumissions en ligne Java.

Utilisation de la mémoire : 42,67 Mo, soit moins de 57,64 % des soumissions en ligne Java.

C'est une solution avec de bonnes performances. Si vous souhaitez être plus élégant, utilisez le traitement streaming, la solution est la suivante :

class Solution {
    public int findPermutationDifference(String s, String t) {
        return IntStream.range(0, s.length())
                   .map(i -> findCharPermutationDifference(s,t,i))
                   .sum();
    }

    public int findCharPermutationDifference(final String s, final String t, final int i) {
        final char c = s.charAt(i);
        final int j = t.indexOf(c);
        return Math.abs(i - j);
    }
}

Durée d'exécution : 5 ms, plus rapide que 2,31 % des soumissions en ligne Java.

Utilisation de la mémoire : 43,02 Mo, soit moins de 23,05 % des soumissions en ligne Java.

Pas aussi bonne que la première solution en termes de performances et de mémoire, mais plus élégante.

—

C'est ça ! N'hésitez pas à commenter si vous avez d'autres questions et faites-moi savoir si j'ai raté quelque chose afin que je puisse mettre à jour en conséquence.

Rendez-vous dans le prochain article ! :)

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!