Pythonの2つの単語間の最小距離

2つの文字列word0とword1とテキストがあるとします。与えられたテキスト内のword0とword1の任意の2つの出現の間の最小距離を見つける必要があります。ここで、距離は単語数で測定されます。それらがテキストに存在しない場合は、-1を返します。

したがって、入力がtext ="cat dog abcd dog cat cat abcd dog wxyz"、word0 ="abcd"、word1 ="wxyz"の場合、"の間に"dog "という単語が1つあるため、出力は1になります。 abcd」と「wxyz」

これを解決するには、次の手順に従います-

• word_list：=テキストからの単語のリスト
• ans：=word_listのサイズ
• L：=null
• 範囲0からword_list-1のサイズのRの場合、実行
  • word_list [R]がword0の場合、またはword_list [R]がword1の場合、
    • Lがnullでなく、word_list[R]がword_list[L]でない場合、
      • ans：=最小のansおよびR --L-1
    • L：=R
• ansがword_listのサイズと同じ場合は-1を返し、それ以外の場合はans

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, text, word0, word1):
      word_list = text.split()
      ans = len(word_list)
      L = None
      for R in range(len(word_list)):
         if word_list[R] == word0 or word_list[R] == word1:
            if L is not None and word_list[R] != word_list[L]:
               ans = min(ans, R - L - 1)
               L = R
      return -1 if ans == len(word_list) else ans
ob = Solution()
text = "cat dog abcd dog cat cat abcd dog wxyz"
word0 = "abcd"
word1 = "wxyz"
print(ob.solve(text, word0, word1))

入力

"cat dog abcd dog cat cat abcd dog wxyz", "abcd", "wxyz"

出力

1