鱼C论坛

 找回密码
 立即注册
查看: 1960|回复: 0

[学习笔记] Leetcode 140. Word Break II

[复制链接]
发表于 2020-7-31 03:32:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

  2. Note:

  3. The same word in the dictionary may be reused multiple times in the segmentation.
  4. You may assume the dictionary does not contain duplicate words.
  5. Example 1:

  6. Input:
  7. s = "catsanddog"
  8. wordDict = ["cat", "cats", "and", "sand", "dog"]
  9. Output:
  10. [
  11.   "cats and dog",
  12.   "cat sand dog"
  13. ]
  14. Example 2:

  15. Input:
  16. s = "pineapplepenapple"
  17. wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
  18. Output:
  19. [
  20.   "pine apple pen apple",
  21.   "pineapple pen apple",
  22.   "pine applepen apple"
  23. ]
  24. Explanation: Note that you are allowed to reuse a dictionary word.
  25. Example 3:

  26. Input:
  27. s = "catsandog"
  28. wordDict = ["cats", "dog", "sand", "and", "cat"]
  29. Output:
  30. []
复制代码

  1. 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

  2. 说明:

  3. 分隔时可以重复使用字典中的单词。
  4. 你可以假设字典中没有重复的单词。
  5. 示例 1:

  6. 输入:
  7. s = "catsanddog"
  8. wordDict = ["cat", "cats", "and", "sand", "dog"]
  9. 输出:
  10. [
  11. "cats and dog",
  12. "cat sand dog"
  13. ]
  14. 示例 2:

  15. 输入:
  16. s = "pineapplepenapple"
  17. wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
  18. 输出:
  19. [
  20. "pine apple pen apple",
  21. "pineapple pen apple",
  22. "pine applepen apple"
  23. ]
  24. 解释: 注意你可以重复使用字典中的单词。
  25. 示例:

  26. 输入:
  27. s = "catsandog"
  28. wordDict = ["cats", "dog", "sand", "and", "cat"]
  29. 输出:
  30. []
复制代码

  1. class Solution:
  2.     def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
  3.         dic = set(wordDict)
  4.         hashmap = {}
  5.         return self.helper(s, dic, hashmap)
  6.    
  7.     def add(sefl, answers: List[str], string: str) -> List[str]:
  8.         result = []
  9.         for answer in answers:
  10.             result.append(answer + " " + string)
  11.         return result
  12.    
  13.     def helper(self, s: str, dic: List[str], hashmap) -> List[str]:
  14.         if s in hashmap:
  15.             return hashmap[s]
  16.         ans = []
  17.         if s in dic:
  18.             ans.append(s)
  19.         for i in range(1, len(s)):
  20.             right = s[i:]
  21.             if right not in dic: continue
  22.             left = s[:i]
  23.             left_list = self.add(self.helper(left, dic, hashmap), right)
  24.             ans = ans + left_list
  25.         hashmap[s] = ans
  26.         return hashmap[s]
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 16:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表