Leetcode — 两个字符串之间的排列差异-java教程-PHP中文网

Leetcode — 两个字符串之间的排列差异

Linda Hamilton

发布： 2025-01-17 22:08:10

原创

799 人浏览过

Leetcode — Permutation Difference between Two Strings

这是一道简单的题目，题意如下：

给定两个字符串 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 代码：

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

登录后复制

运行时间：1 毫秒，快于 100% 的 Java 在线提交。

内存使用：42.67 MB，低于 57.64% 的 Java 在线提交。

这是一个性能良好的解决方案。如果想更优雅一些，使用流式处理，解决方案如下：

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

登录后复制