Leetcode – Permutationsunterschied zwischen zwei Strings

Dies ist eine einfache Frage mit folgender Bedeutung:

Bei zwei Strings s und t kommt jedes Zeichen in s höchstens einmal vor und t ist eine Permutation von s.

Der Permutationsunterschied zwischen s und t ist definiert als die Summe der absoluten Unterschiede zwischen dem Index des Vorkommens jedes Zeichens in s und dem Index seines Vorkommens in t.

Gibt die Permutationsdifferenz zwischen s und t zurück.

Beispiel 1:

Eingabe: s = „abc“, t = „bac“

Ausgabe: 2

Erklärung:

Für s = „abc“ und t = „bac“ ist die Differenz in den Permutationen von s und t gleich der Summe von:

Die absolute Differenz zwischen dem Vorkommensindex von „a“ in

s und dem Vorkommensindex von „a“ in t.

Die absolute Differenz zwischen dem Vorkommensindex von „b“ in

s und dem Vorkommensindex von „b“ in t.

Die absolute Differenz zwischen dem Vorkommensindex von „c“ in

s und dem Vorkommensindex von „c“ in t.

Das heißt, die Permutationsdifferenz zwischen s und t ist gleich |0 - 1|.

Beispiel 2:

Eingabe: s = „abcde“, t = „edbac“

Ausgabe: 12

Erläuterung: Die Permutationsdifferenz zwischen s und t beträgt |1 - |2 - |4 - 0|.

Einschränkungen:

1 ≤ s.length ≤ 100

Jedes Zeichen in

s kommt höchstens einmal vor.

t ist eine Permutation von s.

s enthalten nur englische Kleinbuchstaben.

Die Titelbeschreibung ist lang, aber ein Blick auf ein Beispiel erleichtert das Verständnis des Ziels des Titels.

Je nach Berechnungsmethode der Permutationsdifferenz müssen die folgenden Schritte durchgeführt werden:

• Durchqueren Sie die Zeichenfolge;
• Zeichen basierend auf dem Index abrufen
• Suchen Sie den Index des Zeichens in der zweiten Zeichenfolge
Subtrahieren Sie den zweiten Index vom ersten;
Ermitteln Sie den absoluten Wert dieser Subtraktion und akkumulieren Sie alle Ergebnisse in einer Ausgabe.

Jetzt wandeln wir diese Idee in Java-Code um:

<code class="language-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;
    }
}</code>

Laufzeit: 1 ms, schneller als 100 % der Java-Online-Einreichungen.

Speichernutzung: 42,67 MB, weniger als 57,64 % der Java-Online-Einreichungen.

Dies ist eine Lösung mit guter Leistung. Wenn Sie eleganter sein möchten, verwenden Sie die Streaming-Verarbeitung. Die Lösung lautet wie folgt:

<code class="language-java">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);
    }
}</code>

Laufzeit: 5 ms, schneller als 2,31 % der Java-Online-Einreichungen.

Speichernutzung: 43,02 MB, weniger als 23,05 % der Java-Online-Einreichungen.

Nicht so gut wie die erste Lösung in Bezug auf Leistung und Speicher, aber eleganter.

—

Das ist es! Bitte zögern Sie nicht, einen Kommentar abzugeben, wenn Sie weitere Fragen haben, und lassen Sie mich wissen, wenn ich etwas verpasst habe, damit ich es entsprechend aktualisieren kann.

Bis zum nächsten Artikel! :)

Das obige ist der detaillierte Inhalt vonLeetcode – Permutationsunterschied zwischen zwei Strings. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!