当前位置：首页 > article >正文

LeetCode 3146 两个字符串的排列差

article 2025/1/6 13:49:09

计算字符串的排列差

在算法的世界里，常常会遇到一些有趣又巧妙的题目，今天就来和大家分享一道有关字符串处理与计算的题目，希望能帮助大家加深对字符串操作以及相关算法思维的理解。

题目描述

我们给定了两个字符串 s 和 t，这里有两个重要的前提条件哦。一是每个字符串中的字符都不重复，二呢，t 其实是 s 的一个排列。然后引出了一个很有意思的概念 ——“排列差”。所谓 “排列差”，它被定义为 s 和 t 中每个字符在这两个字符串中位置的绝对差值之和。我们的任务就是要写代码来返回 s 和 t 之间的这个 “排列差” 呀。

解题思路分析

那我们该怎么去解决这个问题呢？其实思路可以分为以下几步：

记录字符位置

首先呀，我们得想办法记录每个字符在两个字符串中出现的位置。这里呢，由于题目假设字符都是英文字母（为了方便讲解，咱们先按小写英文字母举例哦，如果有更广泛的字符范围可以相应调整思路），我们可以利用数组来做这件事。创建两个长度为 26 的整数数组，分别叫做 sIndex 和 tIndex，它们的作用就是对应记录字符串 s 和 t 里每个字符出现的位置索引啦。通过遍历字符串，把每个字符（将字符减去 'a' 就能把它映射到 0 - 25 的索引范围，对应到我们创建的数组下标了哦）所在的位置存到相应的数组中去。比如说，如果 s 字符串里第一个字符是 'b'，那 sIndex['b' - 'a'] 也就是 sIndex[1] 这个位置就会被赋值为 0 （因为是第一个位置嘛）。

计算排列差

在把字符位置都记录好之后呢，接下来就是核心的计算排列差的步骤啦。我们需要再次遍历这两个记录位置的数组，这次遍历的范围就是从 0 到 25 哦，对应着所有可能出现的英文字母。对于那些在 s 或者 t 中出现过的字符（也就是在对应位置数组里值不为 0 的情况啦），我们要计算它们在两个字符串中位置索引的绝对差值，然后把这些差值都累加到一个变量里，咱们这里把这个变量叫做 diffSum 哦。例如，如果某个字符在 s 中的位置是 3 ，在 t 中的位置是 5 ，那它们的绝对差值 Math.abs(3 - 5) 也就是 2 ，就会被累加到 diffSum 中啦。

返回结果

最后呀，把计算得到的 diffSum 返回出去，这个值就是我们要求的字符串 s 和 t 之间的排列差啦。

代码实现示例

下面呢，就是用 Java 语言实现上述思路的代码，一起来看看吧：

class Solution {
    public int findPermutationDifference(String s, String t) {
        int[] sIndex = new int[26];
        int[] tIndex = new int[26];
        // 记录字符串s中字符的位置
        for (int i = 0; i < s.length(); i++) {
            sIndex[s.charAt(i) - 'a'] = i;
        }
        // 记录字符串t中字符的位置
        for (int i = 0; i < t.length(); i++) {
            tIndex[t.charAt(i) - 'a'] = i;
        }
        int diffSum = 0;
        // 遍历位置数组，计算并累加绝对差值
        for (int i = 0; i < 26; i++) {
            if (sIndex[i]!= 0 || tIndex[i]!= 0) {
                diffSum += Math.abs(sIndex[i] - tIndex[i]);
            }
        }
        return diffSum;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "abc";
        String t = "cba";
        int result = solution.findPermutationDifference(s, t);
        System.out.println("排列差为: " + result);
    }
}

`Solution`类中的`findPermutationDifference`方法

初始化位置记录数组：
首先创建了两个长度为 26 的整数数组sIndex和tIndex，用于分别记录字符串s和t中字符出现的位置。这里假设输入的字符串只包含小写英文字母，通过将字符减去'a'来将其映射到 0 - 25 的索引范围，对应数组的下标，方便记录每个字符在字符串中的位置索引。
记录字符串中字符位置：
通过两个for循环，分别遍历字符串s和t。在遍历字符串s时，每当遇到一个字符，就将其在字符串中的位置（也就是当前循环的索引i）记录到sIndex数组中对应的下标位置（通过字符减去'a'得到的下标）。同理，对字符串t进行类似操作，将其字符位置记录到tIndex数组中。
计算排列差：
再使用一个for循环遍历 0 到 25 的索引（对应所有小写英文字母），对于在s或者t中出现过的字符（也就是sIndex或tIndex中对应位置不为 0 的情况），计算该字符在两个字符串中位置索引的绝对差值（使用Math.abs方法获取绝对值），并将这个绝对差值累加到diffSum变量中。
返回排列差结果：
最后，方法返回计算得到的排列差diffSum。

`Main`类中的`main`方法

创建Solution类实例：
在main方法中，首先创建了Solution类的实例，这样就能调用Solution类中定义的findPermutationDifference方法了。
定义测试字符串并调用方法：
接着定义了两个示例字符串s和t，这里只是简单举例用了"abc"和"cba"，你可以替换成任意符合题目要求（字符不重复且一个是另一个的排列）的字符串哦。然后调用solution.findPermutationDifference(s, t)方法来计算这两个字符串之间的排列差，并将结果保存在result变量中。
输出结果：
最后使用System.out.println将计算得到的排列差结果输出显示，方便查看程序运行的结果是否符合预期。

总结与拓展

通过这道题呀，我们不仅练习了对字符串中字符的操作，比如获取字符、定位字符位置这些基础操作，还深入理解了如何根据题目给定的规则去巧妙地设计算法思路，利用数组这种数据结构来辅助我们完成计算。

不过呢，这道题还有可以拓展思考的地方哦。比如要是输入的字符串里字符范围不只是英文字母了，可能包含数字、标点符号等等各种各样的字符，那我们该怎么去调整代码来适应这种更复杂的情况呢？又或者呀，如果要求我们在时间复杂度或者空间复杂度上做进一步优化，那又可以从哪些方面入手呢？大家可以试着去想一想、改一改代码哦，相信这样能让咱们对算法和数据结构的运用更加熟练呢。

好啦，今天这道有趣的算法题目就分享到这里啦，希望大家都有所收获呀，要是有什么疑问或者想法，欢迎在评论区留言讨论哦！

查看全文

http://www.kler.cn/a/464729.html