Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで単語配列の最長のプレフィックスシーケンスを見つけるプログラム

小文字の文字列を含むwという単語のリストがあるとします。 wの最長シーケンスの長さを見つける必要があります。ここで、前の各単語は次の単語のプレフィックスであり、次の単語には1つの新しい文字が追加されます。

したがって、入力がw =["pqr"、 "pq"、 "m"、 "mn"、 "pqrs"]の場合、シーケンスを取得できるため、出力は3になります：["pq"、 " pqr "、" pqrs "]、長さは3です。

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

  • リストを並べ替える
  • dp：=マップ。キーのデフォルト値は0です
  • res：=0
  • wの各単語について、
    • dp [word]：=dp[最後から2番目の要素までの単語の部分文字列]+1
    • res：=resとdp[word]の最大値
  • return res

例

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

from collections import defaultdict
def solve(w):
   w.sort()
   dp = defaultdict(int)
   res = 0
   for word in w:
      dp[word] = dp[word[:-1]] + 1
      res = max(res, dp[word])
   return res

w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))

入力

["pqr", "pq", "m", "mn", "pqrs"]

出力

3

  1. Pythonで連続して増加する最長の部分文字列の長さを見つけるプログラム

    小文字の文字列sがあるとします。これには、英語の文字と「？」が含まれますシンボル。 「？」ごとに削除するか、小文字に置き換える必要があります。文字「a」で始まる、連続して増加する最長の部分文字列の長さを見つける必要があります。 したがって、入力がs =vta ??? defkeの場合、出力は6になります。これは、sを vtabcdefkeに変換でき、 abcdefは、連続して増加する最長の部分文字列であり、これも次のように始まります。 「a」。 これを解決するには、次の手順に従います- maxlen：=0 長さ：=0 qmarks：=0 sの各cについて、 cが「？」と同じ

  2. Pythonのn-aryツリーで最長のパスの長さを見つけるプログラム

    各アイテムが保持しているエッジリスト（u、v）があり、uがvの親であることを表しているとします。ツリー内で最も長いパスの長さを見つける必要があります。パスの長さは、1+そのパス内のノードの数です。 したがって、入力が次のような場合 パスが[1、4、5、7]であり、合計4つのノードがあるため、出力は5になります。したがって、パスの長さは1 + 4=5です。 これを解決するには、次の手順に従います- g：=指定されたエッジリストからのグラフの隣接リスト d：=新しい地図 関数bfs（）を定義します。これには時間がかかります d [o]：=1 f：=o q：=[o]