好资源导航 » 文章资讯 » python求解数组中两个字符串的最小距离

python求解数组中两个字符串的最小距离

2023-09-07 22:26:07 63

题目：

给定一个数组strs，其中的数据都是字符串，给定两个字符串str1，str2。如果这两个字符串都在strs数组中，就返回它们之间的最小距离；如果其中任何一个不在里面，则返回-1；如果两个字符串相等，则返回0。

例如：给定[‘*','3','*','5','10','9','7','1','*']，再给定两个字符串'*‘和'9'，通过函数求得返回值3。

分析：有两种方法

方法1：

遍历数组strs，分别记录两个str1和str2的位置。求得最小的一个距离数字。这样做时间复杂度为o(n^2)。

方法2：

如果查询的次数非常多，为了提高查询的效率，构造Hash表，把每次查询的时间复杂度下降到o(1)。
Python的内置dict类型就是哈希表，实现方法也是hash表，其查询的时间复杂度就是o(1)。哈希表的构造也分很多种：
比如，构造Hash表，key值是strs中的每一个字符串，value值是一个hash表，里面存放着该字符串到其它字符串的最小距离。
写成代码就是：hash_table={“*”:{“3”:1,“5”:1,“10”:2,“9”:3,“7”:2,“1”:1}}
当然这种方法的空间复杂度是o(n^2)

代码：

defmin_distance_1(strs,str1,str2):
'''
数组中两个字符串的最小距离，这是方法1，时间复杂度o(n^2)
:paramstrs:给定的数组中存放有多个字符串
:paramstr1:第一个字符串
:paramstr2:第二个字符串
:return:如果其中给定的一个字符串不在数组strs中，那么返回-1，否则返回两个字符串之间的最小间距
'''
ifstr1notinstrsorstr2notinstrs:
return-1
ifstr1==str2:
return0
dist,min=1,len(strs)
pos1,pos2=0,len(strs)
foriinxrange(0,len(strs)):
ifstr1==strs[i]:
pos1=i
forjinxrange(0,len(strs)):
ifstr2==strs[j]:
pos2=j
dist=abs(pos1-pos2)
ifdist
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

返回顶部
514930285
czq8825@qq.com

python求解数组中两个字符串的最小距离

热门推荐

随机推荐