Python程序查找最长使单词链减少的长度？

假设我们有一个有效单词列表，并且还有一个字符串s，我们必须找到最长的单词减少链的长度，该链可以通过从s开始并删除单个字母而仍然生成有效单词。

因此，如果输入类似于words = [“lii”, “limit”, “limi”, “li”, “coffee”, “jug”, “pool”, “type”] s = “limit”，那么输出将为4，因为我们可以从单词”limit”开始生成链，”limit” -> “limi” -> “lii” -> “li”。

为了解决这个问题，我们将按照以下步骤进行

• 定义一个solve()函数。这将接受words、s参数
• max_num := 0
• 对于每个i在words中，执行以下操作
  • 如果i与s相同，则
    • 对于范围从0到s大小的j，执行以下操作

    • max_num := 1 + solve(words, s[from index 0 to j-1]连接s[from index j + 1 to end])和max_num的最大值

• 返回max_num

更多Python相关文章，请阅读：Python 教程

示例

    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