3146.两个字符串的排列差

【LetMeFly】3146.两个字符串的排列差：小数据，我选择暴力模拟

力扣题目链接：https://leetcode.cn/problems/permutation-difference-between-two-strings/

给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。

排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。

返回 s 和 t 之间的 排列差 。

 

示例 1：

输入：s = "abc", t = "bac"

输出：2

解释：

对于 s = "abc" 和 t = "bac"，排列差是：

• "a" 在 s 中的位置与在 t 中的位置之差的绝对值。
• "b" 在 s 中的位置与在 t 中的位置之差的绝对值。
• "c" 在 s 中的位置与在 t 中的位置之差的绝对值。

即，s 和 t 的排列差等于 |0 - 1| + |2 - 2| + |1 - 0| = 2。

示例 2：

输入：s = "abcde", t = "edbac"

输出：12

解释： s 和 t 的排列差等于 |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12。

 

提示：

• 1 <= s.length <= 26
• 每个字符在 s 中最多出现一次。
• t 是 s 的一个排列。
• s 仅由小写英文字母组成。

解题方法：暴力模拟

使用一个初始值位0的整型变量$ans$记录差值之和。

遍历字符串s中的每一个字符：

对于当前字符s[i]，遍历字符串t。如果t[j]和s[i]相同，则令ans加上$i-j$的绝对值并结束对字符串t的遍历。

最终返回$ans$的值即为答案。

• 时间复杂度$O(len(s)^2)$
• 空间复杂度$O(1)$

字符串的最大长度为26，最多匹配$1+2+3+\cdots+26=\frac{(1+26)\times26}2=351$次，因此使用哈希表的意义不大。

AC代码

C++

class Solution {
public:
    int findPermutationDifference(string s, string t) {
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < t.size(); j++) {
                if (t[j] == s[i]) {
                    ans += abs(i - j);
                    break;
                }
            }
        }
        return ans;
    }
};

Go

package main

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func findPermutationDifference(s string, t string) int {
    ans := 0
    for i := 0; i < len(s); i++ {
        for j := 0; j < len(t); j++ {
            if s[i] == t[j] {
                ans += abs(i - j)
                break
            }
        }
    }
    return ans
}

Java

class Solution {
    public int findPermutationDifference(String s, String t) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            ans += Math.abs(i - t.indexOf(s.charAt(i)));
        }
        return ans;
    }
}

Python

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        ans = 0
        for i in range(len(s)):
            ans += abs(i - t.find(s[i]))
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141497994