Python 中的单词拆分 II

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

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

  • 创建一个 map memo

  • 定义一个名为 solve 的方法，它将获取 string 和 wordDict

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

  • 如果 `s` 在 memo 中，则 -

    • 返回 memo[s]

  • 创建一个数组 ret

  • 对于从 1 到 s 大小的 i

    • 如果 `s` 从索引 0 到 i - 1 的子字符串出现在 wordDict 中，则

      • 对于 solve(`s` 从 i 到末尾的子字符串，wordDict)

      • `p` := `s` 从索引 0 到 i - 1 的子字符串，与空格连接和 j，然后从左右两边清除多余的空格 -

      • 将 p 插入 ret

  • memo[s] := ret

  • 返回 memo[s]

示例

让我们查看以下实现以更好地理解 −

 实时演示

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']

更新于：26-May-2020

416 浏览

开启你的 职业生涯

完成课程即可获得认证

开始
广告