Leetcode — 2 つの文字列間の置換の差

これは次のような意味を持つ簡単な質問です:

2 つの文字列 s と t が与えられた場合、s の各文字は最大 1 回出現し、t は s の順列になります。

s と t の間の順列の差は、s での各文字の出現インデックスと t でのその出現インデックスの間の絶対差の合計として定義されます。

s と t の間の順列の差を返します。

例 1:

入力: s = "abc"、t = "bac"

出力: 2

説明:

s = "abc" および t = "bac" の場合、s と t の順列の差は次の合計に等しくなります。

s での「a」の出現インデックスと t での「a」の出現インデックス間の絶対差。

s の「b」の出現インデックスと t の「b」の出現インデックスの間の絶対差。

s の「c」の出現インデックスと t の「c」の出現インデックスの間の絶対差。

つまり、s と t の置換差は |0 - 1| |1 - 0| |2 - 2| に等しくなります。

例 2:

入力: s = "abcde"、t = "edbac"

出力: 12

説明: s と t の順列の差は |0 - 3| |1 - 2| |3 - 1| = 12 となります。

制約:

1 ≤ s.length ≤ 100

内の各文字は最大 1 回出現します。

t は s の順列です。

には英小文字のみが含まれます。

タイトルの説明は長くなっていますが、例を見るとタイトルの目的が理解しやすくなります。

順列差の計算方法に従って、次の手順を実行する必要があります:

• 文字列をトラバースします。
• インデックスに基づいて文字を取得します。
• 2 番目の文字列内の文字のインデックスを検索します。
• 最初のインデックスから 2 番目のインデックスを減算します;
• この減算の絶対値を取得し、すべての結果を 1 つの出力に累積します。

次に、このアイデアを 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;
    }
}

実行時間: 1ms、Java オンライン送信の 100% よりも高速です。

メモリ使用量: 42.67 MB、Java オンライン提出の 57.64% よりも低い。

これは優れたパフォーマンスを備えたソリューションです。よりエレガントにしたい場合は、ストリーミング処理を使用します。解決策は次のとおりです:

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);
    }
}

実行時間: 5 ミリ秒、Java オンライン送信の 2.31% よりも高速です。

メモリ使用量: 43.02 MB、Java オンライン提出の 23.05% 未満。

パフォーマンスとメモリの点では最初のソリューションほど良くはありませんが、よりエレガントです。

—

それだけです！他にご質問がございましたら、お気軽にコメントしてください。何か見逃している場合はお知らせください。それに応じて更新できるようにします。

次の記事でお会いしましょう! :)

以上がLeetcode — 2 つの文字列間の置換の差の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。