pythonソルバー配列中の2つの文字列の最小距離


タイトル:
配列stsが与えられています。データはすべて文字列で、二つの文字列str 1、str 2が与えられています。この2つの文字列がsts配列にある場合、それらの間の最小距離を返します。どちらかが中にいない場合、-1に戻ります。2つの文字列が等しい場合、0を返します。
例えば、「*」、「3」、「5」、「10」、「9」、「7」、「1」、「*」の2つの文字列を与え、関数によって3を返します。
二つの方法があります。
方法1:
配列stsを経て、二つのstr 1とstr 2の位置を記録します。最小の距離の数字を求める。このようにする時間の複雑さはo(n^2)です。
方法2: 
検索の回数が非常に多い場合は、クエリの効率を向上させるために、Hashテーブルを作成し、クエリー毎の時間複雑度をo(1)に下げる。 
Pythonの内蔵dictタイプはハッシュ・テーブルであり、実装方法もhashテーブルであり、クエリの時間複雑さはo(1)である。ハッシュ・テーブルの構造も様々です。 
例えば、Hashテーブルを構成し、key値はstsの各文字列であり、value値はhashテーブルであり、その中には他の文字列までの最小距離が格納されている。 
コードにすると、hash_です。テーブル={*}:{3}:1、“5”:1,“10”:2,“9”:3,“7”:2,“1”:1} 
もちろんこの方法の空間複雑度はo(^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]
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。