Python_最短單詞距離

python

QQ 2021-04-13 17:25:03 ‧ 1840 瀏覽

題目描述：給定一個 String 形態的 List，找出此 List 中有重複字詞的最近距離。
（其中 "a" 有重複，index 分別是2,5,8，所以最短距離為3。）

input：words = ["I","am","a","student","from","a","university","in","a","city"]
output：3

這是我用 two pointer 概念加入兩個參數 word1,word2 的結果，可正確執行

import sys
def find_nearest_repeated_word(s:list, word1:str, word2:str)->int:
    
    if s == None or word1 == None or word2 == None:
        return -1

    idx1 = -1
    idx2 = -1
    minDiff = sys.maxsize

    for i in range(len(s)):
        if s[i] == word1:
            idx1 = i

        if s[i] == word2:
            idx2 = i

        if idx1 != -1 and idx2 != -1:
            minDiff = min(minDiff, abs(idx1 - idx2))

    return minDiff

但題目的要求是必須在沒有指定單字時（如下，也就是不需輸入word1、word2時），直接找出最近的重複單字，希望厲害的大家可以給新手一點提點 ><。

print(find_nearest_repeated_word(["I","am","a","student","from","a","university","in","a","city"]))
ANS = 3

tunin iT邦新手 4 級 ‧ 2021-04-13 18:30:40 檢舉

用個 dictionary，以每個單詞當key、出現的位置已array紀錄當作value去存，之後再去找出有重複出現單詞，計算最短距離。

小魚 iT邦大師 1 級 ‧ 2021-04-13 19:45:07 檢舉

先不要寫程式, 先思考你需要哪些變數來存資料, 先寫下來, 再把你寫的轉換成程式.

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

1 個回答

一級屠豬士

iT邦大師 1 級 ‧ 2021-04-13 22:38:26

最佳解答

from collections import defaultdict
import itertools

words = ["I","am","a","student","from","a","university","in","a","city"]

d = defaultdict(list)

for i in range(len(words)):
  d[words[i]].append(i)


print(sorted(d.items()))
print()

new_dict = {}

for k, v in d.items():
  if len(v) > 1:
    new_dict[k] = v

print(new_dict)
print('-' * 10)

for k, v in new_dict.items():
  new_list = []
  p = itertools.product(v,v)
  for v1, v2 in p:
    if v1 != v2 :
      new_list.append(abs(v1 - v2))
  
  short = min(new_list)
  print(k , '(short distance)--> ', short)

執行結果:

python3 p0413.py
[('I', [0]), ('a', [2, 5, 8]), ('am', [1]), ('city', [9]), ('from', [4]), ('in', [7]), ('student', [3]), ('university', [6])]

{'a': [2, 5, 8]}
----------
a (short distance)-->  3