aboutsummaryrefslogtreecommitdiff
path: root/word_break2.py
diff options
context:
space:
mode:
Diffstat (limited to 'word_break2.py')
-rw-r--r--word_break2.py49
1 files changed, 49 insertions, 0 deletions
diff --git a/word_break2.py b/word_break2.py
new file mode 100644
index 0000000..7c741c8
--- /dev/null
+++ b/word_break2.py
@@ -0,0 +1,49 @@
+# 140. Word Break II
+
+"""
+given a string 's' and a dictionary of strings 'wordDict', add spaces in 's'
+to construct a sentence where each word is a valid dictionary word. return
+all such possible sentences in any order. note that the same word in the
+dictionary may be reused mutliple times in the segmentation.
+"""
+
+
+class Solution(object):
+ def dfs(self, s, wordDict, memo):
+ if s in memo:
+ return memo[s]
+ if not s:
+ return []
+ res = []
+ for word in wordDict:
+ if not s.startswith(word):
+ continue
+ if len(word) == len(s):
+ res.append(word)
+ else:
+ res_rest = self.dfs(s[len(word) :], wordDict, memo)
+ for item in res_rest:
+ item = word + " " + item
+ res.append(item)
+ memo[s] = res
+ return res
+
+ def wordBreak(self, s, wordDict):
+ """
+ :type s: str
+ :type wordDict: List[str]
+ :rtype: List[str]
+ """
+ return self.dfs(s, wordDict, {})
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.wordBreak(s="catsanddog", wordDict=["cat", "cats", "and", "sand", "dog"]))
+ print(
+ obj.wordBreak(
+ s="pineapplepenapple",
+ wordDict=["apple", "pen", "applepen", "pine", "pineapple"],
+ )
+ )
+ print(obj.wordBreak(s="catsandog", wordDict=["cats", "dog", "sand", "and", "cat"]))