Pythonで最も長く減少するワードチェーンの長さを見つけるプログラム？

有効な単語のリストがあり、文字列sもあるとすると、sから始めて単一文字を削除することで生成できる、減少する単語の最長チェーンの長さを見つけて、有効な単語を作成する必要があります。

したがって、入力がwords =["lii"、 "limit"、 "limi"、 "li"、 "coffee"、 "jug"、 "pool"、 "type"] s ="limit"の場合、 「limit」、「limit」->「limi」->「lii」->「li」という単語からチェーンを作成できるため、出力は4になります。

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

• 関数solve（）を定義します。これには言葉が必要です、s

• max_num：=0

• 言葉で言うと、iごとに

  • iがsと同じ場合、

    • 0からsのサイズの範囲のjについては、次のようにします

      • max_num：=最大1 + solution（words、s [from index 0 to j-1] concatenate s [from index j + 1 to end]）and max_num

• max_numを返す

例

class Solution:
   def solve(self, words, s):
      max_num = 0
      for i in words:
         if i == s:
            for j in range(len(s)):
               max_num = max(1 + self.solve(words, s[:j] + s[j + 1 :]), max_num)
      return max_num

ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))

入力

["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"],"limit"

出力

4