題目：

給定一個(gè)數(shù)組 strs，其中的數(shù)據(jù)都是字符串，給定兩個(gè)字符串 str1，str2。如果這兩個(gè)字符串都在 strs數(shù)組中，就返回它們之間的最小距離；如果其中任何一個(gè)不在里面，則返回 -1；如果兩個(gè)字符串相等，則返回 0。

例如：給定[‘*','3','*','5','10','9','7','1','*']，再給定兩個(gè)字符串'* ‘和'9'，通過(guò)函數(shù)求得返回值 3。

分析：有兩種方法

方法1：

遍歷數(shù)組 strs，分別記錄兩個(gè) str1 和 str2 的位置。求得最小的一個(gè)距離數(shù)字。這樣做時(shí)間復(fù)雜度為 o(n^2)。

方法2： 

如果查詢的次數(shù)非常多，為了提高查詢的效率，構(gòu)造Hash表，把每次查詢的時(shí)間復(fù)雜度下降到 o(1)。 
Python 的內(nèi)置 dict 類型就是哈希表，實(shí)現(xiàn)方法也是hash 表，其查詢的時(shí)間復(fù)雜度就是 o(1)。哈希表的構(gòu)造也分很多種： 
比如，構(gòu)造 Hash 表，key值是strs中的每一個(gè)字符串，value值是一個(gè)hash表，里面存放著該字符串到其它字符串的最小距離。 
寫(xiě)成代碼就是：hash_table = {“*”:{“3”:1, “5”:1, “10”:2, “9”:3, “7”:2, “1”:1}} 
當(dāng)然這種方法的空間復(fù)雜度是 o(n^2)

代碼： 

 def min_distance_1(strs, str1, str2):  '''  數(shù)組中兩個(gè)字符串的最小距離，這是方法1，時(shí)間復(fù)雜度 o(n^2)  :param strs: 給定的數(shù)組中存放有多個(gè)字符串  :param str1: 第一個(gè)字符串  :param str2: 第二個(gè)字符串  :return: 如果其中給定的一個(gè)字符串不在數(shù)組 strs 中，那么返回-1，否則返回兩個(gè)字符串之間的最小間距  '''  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):  '''  數(shù)組中兩個(gè)字符串的最小距離，這是方法2，如果查詢的次數(shù)非常多，把每次查詢的時(shí)間復(fù)雜度下降到 o(1)。  Python 的內(nèi)置 dict 類型就是哈希表，實(shí)現(xiàn)方法也是hash 表，其查詢的時(shí)間復(fù)雜度就是 o(1)。哈希表的構(gòu)造也分很多種：  比如，構(gòu)造 Hash 表，key值是strs中的每一個(gè)字符串，value值是一個(gè)hash表，里面存放著該字符串到其它字符串的最小距離。   寫(xiě)成代碼就是：hash_table = {"*":{"3":1, "5":1, "10":2, "9":3, "7":2, "1":1}}  當(dāng)然這種方法的空間復(fù)雜度是 o(n^2)  :param strs: 給定的數(shù)組中存放有多個(gè)字符串['*','3','*','5','10','9','7','1','*']  :param str1: 第一個(gè)字符串, '*'  :param str2: 第二個(gè)字符串, '9'  :return: 如果其中給定的一個(gè)字符串不在數(shù)組 strs 中，那么返回-1，否則返回兩個(gè)字符串之間的最小間距  '''  if str1 not in strs or str2 not in strs:   return -1  if str1 == str2:   return 0  def create_hash(strs): # 創(chuàng)建 hash 的過(guò)程并不在查詢里   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]