LeetCode 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的整型变量 a n s ans ans记录差值之和。
遍历字符串s中的每一个字符:
对于当前字符s[i],遍历字符串t。如果t[j]和s[i]相同,则令ans加上 i − j i-j i−j的绝对值并结束对字符串t的遍历。
最终返回 a n s ans ans的值即为答案。
- 时间复杂度 O ( l e n ( s ) 2 ) O(len(s)^2) O(len(s)2)
- 空间复杂度 O ( 1 ) O(1) O(1)
字符串的最大长度为26,最多匹配 1 + 2 + 3 + ⋯ + 26 = ( 1 + 26 ) × 26 2 = 351 1+2+3+\cdots+26=\frac{(1+26)\times26}2=351 1+2+3+⋯+26=2(1+26)×26=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 mainfunc abs(x int) int {if x < 0 {return -x}return x
}func findPermutationDifference(s string, t string) int {ans := 0for 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 = 0for i in range(len(s)):ans += abs(i - t.find(s[i]))return ans
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/141497994