Python求解数组中两个字符串的最小距离：两种算法实现与复杂度分析

苏见山

发布时间：2026-10-13 | 5人浏览过

原创

本文介绍在Python中求解数组内两个指定字符串最小距离的两种方法。第一种为暴力遍历法，时间复杂度为O(n^2)；第二种利用Python内置dict构建哈希表预计算距离，将查询复杂度降至O(1)，但空间复杂度升至O(n^2)。文章提供了完整代码示例及适用场景分析，帮助开发者根据查询频率选择最优方案。

题目要求：

给定一个包含字符串的数组strs，以及两个目标字符串str1和str2。若这两个字符串均存在于数组中，需返回它们之间的最小距离；若任一字符串不存在，则返回-1；若两个字符串完全相同，则返回0。

示例说明：假设数组为['*','3','*','5','10','9','7','1','*']，目标字符串为'* '和'9'，通过函数计算得到的最小距离值为3。

解题思路：本文提供两种不同的解决策略。

方法一：

直接遍历数组strs，分别记录str1和str2出现的位置索引，并计算所有可能组合中的最小距离。该方法的实现逻辑简单，但时间复杂度较高，为O(n^2)。

方法二：

针对高频查询场景，为提升效率，可预先构建哈希表，将单次查询的时间复杂度降低至O(1)。Python内置的dict类型即为哈希表实现，查询时间复杂度为O(1)。哈希表的构建方式多样，例如：以strs中的每个字符串作为key，value为另一个哈希表，存储该字符串到数组中其他所有字符串的最小距离。代码示意如下：hash_table = {“*”:{“3”:1, “5”:1, “10”:2, “9”:3, “7”:2, “1”:1}}。需要注意的是，这种预计算方式的空间复杂度为O(n^2)。

代码实现：

 def min_distance_1(strs, str1, str2):
  '''
  数组中两个字符串的最小距离，这是方法1，时间复杂度 o(n^2)
  :param strs: 给定的数组中存放有多个字符串
  :param str1: 第一个字符串
  :param str2: 第二个字符串
  :return: 如果其中给定的一个字符串不在数组 strs 中，那么返回-1，否则返回两个字符串之间的最小间距
  '''
  if str1 not in strs or str2 not in strs:
   return -1
  if str1 == str2:
   return 0
  dist, min = 1, len(strs)
  pos1, pos2 = 0, len(strs)
  for i in xrange(0, len(strs)):
   if str1 == strs[i]:
    pos1 = i
    for j in xrange(0, len(strs)):
     if str2 == strs[j]:
      pos2 = j
     dist = abs(pos1 - pos2)
     if dist < min:
      min = dist
  return min

 def min_distance_2(strs, str1, str2):
  '''
  数组中两个字符串的最小距离，这是方法2，如果查询的次数非常多，把每次查询的时间复杂度下降到 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)
  :param strs: 给定的数组中存放有多个字符串['*','3','*','5','10','9','7','1','*']
  :param str1: 第一个字符串, '*'
  :param str2: 第二个字符串, '9'
  :return: 如果其中给定的一个字符串不在数组 strs 中，那么返回-1，否则返回两个字符串之间的最小间距
  '''
  if str1 not in strs or str2 not in strs:
   return -1
  if str1 == str2:
   return 0

  def create_hash(strs): # 创建 hash 的过程并不在查询里
   strs_set = list(set(strs))
   dist_hash = {}
   for i in xrange(0, len(strs_set)):
    temp = {}
    for j in xrange(0, len(strs_set)):
     if strs_set[i] != strs_set[j]:
      dist = min_distance_1(strs, strs_set[i], strs_set[j])
      temp[strs_set[j]] = dist
    dist_hash[strs_set[i]] = temp
   return dist_hash

  return create_hash(strs)[str1][str2]

以上即为本文的全部内容，希望对读者的学习有所帮助，同时也欢迎大家继续支持本站。