Python中的Word Break II

假设我们有一个非空字符串s和一个名为wordDict的字典，该字典包含一个非空单词列表，在s中添加空格以构成一个句子，其中每个单词都是有效的字典单词。我们必须找到所有可能的句子。“ appleraincoat”和字典为[“ app”，“ apple”，“ rain”，“ coat”，“ raincoat”]

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

• 创建一个映射备忘录

• 定义一个名为Solve的方法，它将使用字符串和wordDict

• 如果s为null，则返回空列表

• 如果在备忘录中，则-

• 返回备忘录

• 创建一个数组ret

• 对于范围1到s的i

• 对于solve中的j（从i到s的子字符串，wordDict）

• p：= s的子串，从索引0到i – 1，由空格和j连接，然后从左右清除多余的空间-

• 将p插入ret

• 如果在wordDict中存在从索引0到i – 1的s的子字符串，则

• 备忘：= ret

• 返回备忘录

示例

让我们看下面的实现以更好地理解-

class Solution(object):
   def wordBreak(self, s, wordDict):
      self.memo = {}
      wordDict = set(wordDict)
      return self.solve(s,wordDict)
   def solve(self,s, wordDict):
      if not s:
         return ['']
      if s in self.memo:
         return self.memo[s]
      ret = []
      for i in range(1,len(s)+1):
         if s[:i] in wordDict:
            for j in self.solve(s[i:],wordDict):
               ret.append((s[:i] + " " + j).strip())
      self.memo[s] = ret
      return self.memo[s]

ob = Solution()print(ob.wordBreak("appleraincoat",["app","apple","rain","coat","rain coat"]))

输入值

"appleraincoat"
["app","apple","rain","coat","raincoat"]

输出结果

['apple rain coat', 'apple raincoat']