Leetcode — Permutasi Perbezaan antara Dua Rentetan

Ini adalah soalan mudah dengan maksud berikut:

Diberi dua rentetan s dan t, setiap aksara dalam s muncul paling banyak sekali dan t ialah pilih atur s.

Perbezaan pilihatur antara s dan t ditakrifkan sebagai jumlah perbezaan mutlak antara indeks kejadian setiap aksara dalam s dan indeks kejadiannya dalam t.

Mengembalikan perbezaan pilih atur antara s dan t.

Contoh 1:

Input: s = "abc", t = "bac"

Output: 2

Penjelasan:

Untuk s = "abc" dan t = "bac", perbezaan dalam pilih atur s dan t adalah sama dengan hasil tambah:

Perbezaan mutlak antara indeks kejadian "a" dalam

s dan indeks kejadian "a" dalam t.

Perbezaan mutlak antara indeks kejadian "b" dalam

s dan indeks kejadian "b" dalam t.

Perbezaan mutlak antara indeks kejadian "c" dalam

s dan indeks kejadian "c" dalam t.

Iaitu, perbezaan permutasi antara s dan t adalah sama dengan |0 - 1| |2 - 2|.

Contoh 2:

Input: s = "abcde", t = "edbac"

Output: 12

Penjelasan: Perbezaan permutasi antara s dan t adalah bersamaan dengan |0 - 3| |2 - 4|.

Kekangan:

1 ≤ s.panjang ≤ 100

Setiap aksara dalam

s muncul paling banyak sekali.

t ialah pilih atur bagi s.

hanya mengandungi huruf kecil Inggeris.

Huraian tajuk adalah panjang, tetapi melihat contoh akan memudahkan untuk memahami matlamat tajuk.

Mengikut kaedah pengiraan perbezaan pilih atur, langkah berikut perlu dilakukan:

• Melintasi rentetan
• Dapatkan semula aksara berdasarkan indeks;
Cari indeks aksara dalam rentetan kedua;
• Tolak indeks kedua daripada yang pertama;
• Dapatkan nilai mutlak penolakan ini dan kumpulkan semua keputusan ke dalam satu output.
Sekarang mari tukar idea ini kepada kod Java:

<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>

Masa tayangan: 1ms, lebih pantas daripada 100% penyerahan dalam talian Java.

Penggunaan memori: 42.67 MB, lebih rendah daripada 57.64% penyerahan dalam talian Java.

Ini adalah penyelesaian dengan prestasi yang baik. Jika anda ingin lebih elegan, gunakan pemprosesan streaming, penyelesaiannya adalah seperti berikut:

<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>

Masa tayangan: 5ms, lebih pantas daripada 2.31% penyerahan dalam talian Java.

Penggunaan memori: 43.02 MB, kurang daripada 23.05% penyerahan dalam talian Java.

Tidak sebaik penyelesaian pertama dari segi prestasi dan ingatan, tetapi lebih elegan.

—

Itu sahaja! Sila berasa bebas untuk mengulas jika anda mempunyai sebarang soalan lain dan beritahu saya jika saya terlepas sesuatu supaya saya boleh mengemas kini dengan sewajarnya.

Jumpa anda dalam artikel seterusnya! :)

Atas ialah kandungan terperinci Leetcode — Permutasi Perbezaan antara Dua Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!