Leetcode 140. Word Break II

Problem

Leetcode 140 - Word Break II

Example:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

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.

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Approach

We can use backtracking method, and when iterate through s, once we find a word in wordDict, then we can add it to current array. Once we reach the end of s, we can append it to res as a string

Here is the Python code for the solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)
        curr = []
        res = []

        def dfs(i):
            if i == len(s):
                res.append(' '.join(curr))
                return

            for j in range(i, len(s)):
                w = s[i:j+1]
                if w in wordDict:
                    curr.append(w)
                    dfs(j+1)
                    curr.pop()

        dfs(0)
        return res  

Time Complexity and Space Complexity

Time Complexity: $O(m + n*2^n)$

Space Complexity: $O(m + 2^n)$