Python程序：检查字符串能否被给定单词列表分解

假设我们有一个单词列表和另一个没有空格的字符串s。我们必须检查该字符串是否可以使用单词列表进行分解。

因此，如果输入类似于 words = ["love", "python", "we", "programming", "language"] s = "welovepythonprogramming"，则输出将为 True

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

  • words := 所有唯一单词的新集合
  • 定义一个函数 rec()。这将取 i
  • 如果 i 等于 s 的大小，则
    • 返回 True
  • acc := 空字符串
  • 对于从 i 到 s 大小的范围内的 j，执行以下操作：
    • acc := acc 连接 s[j]
    • 如果 acc 存在于 words 中，则
      • 如果 rec(j + 1) 为 True，则
        • 返回 True
  • 返回 False
  • 从主方法调用 rec(0) 并返回结果

让我们看看下面的实现，以便更好地理解：

示例

在线演示

class Solution:
   def solve(self, words, s):
      words = set(words)

      def rec(i=0):
         if i == len(s):
            return True
         acc = ""
         for j in range(i, len(s)):
            acc += s[j]
            if acc in words:
               if rec(j + 1):
                  return True
         return False

      return rec()
     
ob = Solution()
words = ["love", "python", "we", "programming", "language"]
s = "welovepythonprogramming"
print(ob.solve(words, s))

输入

["love", "python", "we", "programming", "language"], "welovepythonprogramming"

输出

True

更新于：2020年12月2日

527 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告