Leetcode — 兩個字串之間的排列差異

這是一道簡單的題目，題意如下：

給定兩個字串 s 和 t，其中 s 中的每個字元最多出現一次，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。

範例 2：

輸入：s = “abcde”，t = “edbac”

輸出：12

解釋：s 和 t 之間的排列差異等於 |0 - 3| |1 - 2| |2 - 4| |3 - 1| |4 - 0| = 12。

約束條件：

1 ≤ s.length ≤ 100

s 中每個字元最多出現一次。

t 是 s 的一個排列。

s 只包含小寫英文字母。

題目描述冗長，但看一個例子就能更容易理解題目的目標。

根據排列差異的計算方法，需要執行以下步驟：

• 遍歷字串；
• 依索引檢索字元；
• 在第二個字串中找出該字元的索引；
• 用第一個索引減去第二個索引；
• 取得該減法的絕對值，並將所有結果累加到一個輸出中。

現在讓我們將這個思路轉換成 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;
    }
}

運行時間：1 毫秒，快於 100% 的 Java 線上提交。

記憶體使用：42.67 MB，低於 57.64% 的 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);
    }
}

運行時間：5 毫秒，快於 2.31% 的 Java 線上提交。

記憶體使用：43.02 MB，低於 23.05% 的 Java 線上提交。

效能和記憶體方面不如第一個方案，但更優雅。

—

就是這樣！如有其他問題，請隨時評論，如果我遺漏了什麼，請告訴我，以便我可以相應地更新。

下篇文章再見！ :)

以上是Leetcode — 兩個字串之間的排列差異的詳細內容。更多資訊請關注PHP中文網其他相關文章！