iT邦幫忙

0

Python_最短單詞距離

QQ 2021-04-13 17:25:03841 瀏覽

題目描述:給定一個 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邦新手 5 級 ‧ 2021-04-13 18:30:40 檢舉
用個 dictionary,以每個單詞當key、出現的位置已array紀錄當作value去存,之後再去找出有重複出現單詞,計算最短距離。
小魚 iT邦大師 1 級 ‧ 2021-04-13 19:45:07 檢舉
先不要寫程式, 先思考你需要哪些變數來存資料, 先寫下來, 再把你寫的轉換成程式.

1 個回答

3
一級屠豬士
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
看更多先前的回應...收起先前的回應...

好人就幫到底嗎
/images/emoticon/emoticon25.gif

好吧,修改一下.

QQ iT邦新手 5 級 ‧ 2021-04-14 00:36:35 檢舉

有!我改了一下有成功了,謝謝解惑~
/images/emoticon/emoticon32.gif

太好了! 繼續努力加油 !

大家都好棒棒
/images/emoticon/emoticon12.gif

我要發表回答

立即登入回答