用 Python 编写程序来查找最长递减词链的长度?

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

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

为了解决这个问题，我们将遵循以下步骤

• 定义一个函数solve()。这将获取单词 s

• max_num := 0

• 对于单词中的每个 i，执行

  • 如果 i 与 s 相同，则

    • 对于范围从 0 到 s 大小的 j，执行

      • max_num := 最大值 1 + 解决(单词，s[从索引 0 到 j-1] 连接 s[从索引 j + 1 到结束])和 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

相关文章

• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?
• 如何使用 Python 和 openpyxl 在 excel 中创建图表?
• 用 Python 编写程序来找出斐波那契数列中最小的和为 n 的数?
• 用 Python 执行 excel 电子表格操作的程序?
• 如何在 Python 中将数据值插入字符串?
• 用 Python 编写程序来计算将所有值转换为相同值所需的操作次数?
• 用 Python 编写程序检查是否可以将两个分区分成总和相等的组?
• 如何在 Python 中添加命令行参数?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/