leetcode 3146 两个字符串的排列差
leetcode 3146 两个字符串的排列差
- 正文
- 题目描述
- 解题思路
- 方法1
- Python 处理字符串的思路
- 方法2
正文
题目描述
解题思路
直接 for 循环遍历第一个字符串，在第二个字符串中找出第一个字符串中的对应字符的位置，做差，再取绝对值，最后求和即可。
方法1
class Solution:def findPermutationDifference(self, s: str, t: str) -> int:sum_ = 0for index, char in enumerate(s):sum_ += abs(index - t.index(char))return sum_
上述代码可以实现目的，但是 index() 方法也是一个遍历的过程，会导致代码需要的时间很长。
Python 处理字符串的思路
Python 中使用字典处理字符串就可以避免使用 index() 进入循环，本题中可以缩减至少一半的时间。
方法2
class Solution:def findPermutationDifference(self, s: str, t: str) -> int:dict1 = {}for i, char in enumerate(s):dict1[char] = isum_ = 0for i, char in enumerate(t):sum_ += abs(i - dict1[char])return sum_上述代码我们用了两次循环，且使用了累加的方式，每次循环进行一次加法运算，这样就会增加时间。
我们可以尝试使用行内循环将累加变成对 generator 对象的一次性求和，可以减少时间，且无需初始化一个额外的变量 sum_。
class Solution:def findPermutationDifference(self, s: str, t: str) -> int:dict1 = {c: i for i, c in enumerate(s)}return sum(abs(i - dict1[c]) for i, c in enumerate(t))
如果大家觉得有用，就请点个赞吧~