|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- 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.
- Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
- Example 1:
- Input:
- s = "catsanddog"
- wordDict = ["cat", "cats", "and", "sand", "dog"]
- Output:
- [
- "cats and dog",
- "cat sand dog"
- ]
- Example 2:
- Input:
- s = "pineapplepenapple"
- wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
- Output:
- [
- "pine apple pen apple",
- "pineapple pen apple",
- "pine applepen apple"
- ]
- Explanation: Note that you are allowed to reuse a dictionary word.
- Example 3:
- Input:
- s = "catsandog"
- wordDict = ["cats", "dog", "sand", "and", "cat"]
- Output:
- []
复制代码
- 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
- 说明:
- 分隔时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
- 示例 1:
- 输入:
- s = "catsanddog"
- wordDict = ["cat", "cats", "and", "sand", "dog"]
- 输出:
- [
- "cats and dog",
- "cat sand dog"
- ]
- 示例 2:
- 输入:
- s = "pineapplepenapple"
- wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
- 输出:
- [
- "pine apple pen apple",
- "pineapple pen apple",
- "pine applepen apple"
- ]
- 解释: 注意你可以重复使用字典中的单词。
- 示例:
- 输入:
- s = "catsandog"
- wordDict = ["cats", "dog", "sand", "and", "cat"]
- 输出:
- []
复制代码
- class Solution:
- def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
- dic = set(wordDict)
- hashmap = {}
- return self.helper(s, dic, hashmap)
-
- def add(sefl, answers: List[str], string: str) -> List[str]:
- result = []
- for answer in answers:
- result.append(answer + " " + string)
- return result
-
- def helper(self, s: str, dic: List[str], hashmap) -> List[str]:
- if s in hashmap:
- return hashmap[s]
- ans = []
- if s in dic:
- ans.append(s)
- for i in range(1, len(s)):
- right = s[i:]
- if right not in dic: continue
- left = s[:i]
- left_list = self.add(self.helper(left, dic, hashmap), right)
- ans = ans + left_list
- hashmap[s] = ans
- return hashmap[s]
复制代码 |
|