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

yipeiwu_com7年前Python基础

题目:

给定一个数组 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)

代码: 

 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]

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

实践Vim配置python开发环境

这段时间一直在用Python自带的IDLE编辑器、可是这IDLE的代码缩进真的让人很受伤、当你用到if:elif:的时候、后一行的elif:不会自动对齐、这让我经常出现在调试的时候才发现...

将Emacs打造成强大的Python代码编辑工具

将Emacs打造成强大的Python代码编辑工具

基本配置 Emacs本身提供了python-mode,输入M-x python-mode,就可以进入python模式。相应地,会在菜单栏出现Python菜单。当然,一般来讲,如果是.py...

深入理解Python 代码优化详解

深入理解Python 代码优化详解

 选择了脚本语言就要忍受其速度,这句话在某种程度上说明了 python 作为脚本的一个不足之处,那就是执行效率和性能不够理想,特别是在 performance 较差的机器上,因此有必要进...

Python参数解析模块sys、getopt、argparse使用与对比分析

Python参数解析模块sys、getopt、argparse使用与对比分析

一些命令行工具的使用能够大大简化代码脚本的维护成本,提升复用性,今天主要是借助于python提供的几种主流的参数解析工具来实现简单的功能,主要是学习实践为主,这是新年伊始开工的第一篇,还...

Python实现K折交叉验证法的方法步骤

学习器在测试集上的误差我们通常称作“泛化误差”。要想得到“泛化误差”首先得将数据集划分为训练集和测试集。那么怎么划分呢?常用的方法有两种,k折交叉验证法和自助法。介绍这两种方法的资料有很...