diff options
Diffstat (limited to 'word_break2.py')
-rw-r--r-- | word_break2.py | 49 |
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"])) |