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

• 对于 words 中的每个 i，执行以下操作：

  • 如果 i 与 s 相同，则执行以下操作：

    • 对于从 0 到 s 大小的范围内的每个 j，执行以下操作：

      • max_num := 1 + solve(words, 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

Arnab Chakraborty

更新于: 2020年11月10日

155 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始