Question

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:
[]

Solution 1: Backtracking

Worst case time complexity is \(O(n^n)\), so it is TLE.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        res = list()
        self.backtracking(s, wordDict, len(s), res, [], 0)
        return res

    def backtracking(self, s, wordDict, length, res, partial, index):
        if index == length:
            res.append(' '.join(partial))
        else:
            for end in range(index + 1, length + 1):
                if s[index: end] in wordDict:
                    self.backtracking(s, wordDict, length, res, partial + [s[index: end]], end)

Solution 2: DP

\(O(n^3)\) complexity. It is prone to TLE if the string is long but not breakable.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        if len(s) == 0 or len(wordDict) == 0:
            return []
        if not self.wordBreak1(s, wordDict):
            return []

        dp = list()
        dp.append([])
        wordDict = set(wordDict)
        max_len = max([len(word) for word in wordDict])

        for i in range(1, len(s) + 1):
            res = list()
            for j in range(i - 1, max(-1, i - max_len - 1), -1):
                if s[j:i] in wordDict:
                    if j == 0:
                        res.append(s[j:i])
                    elif len(dp[j]) != 0:
                        for partial in dp[j]:
                            res.append("{} {}".format(partial, s[j:i]))
            dp.append(res)

        return dp[-1]