We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Word Break II

Difficulty: Hard

Problem Description

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 multiple times in the segmentation.

Key Insights

  • The problem can be approached using backtracking to explore all possible segmentations of the string.
  • A memoization technique can be used to store previously computed results to avoid redundant calculations.
  • The solution needs to handle cases where no valid segmentation exists, returning an empty list.

Space and Time Complexity

Time Complexity: O(N^2 * M) where N is the length of the string and M is the number of words in the dictionary. Space Complexity: O(N) for the recursion stack and O(N) for the memoization storage.

Solution

The solution employs a backtracking algorithm to explore all possible segmentations of the input string. The algorithm checks each substring against the dictionary to determine if it is a valid word. If a valid word is found, the algorithm recursively processes the remaining substring. Memoization is used to store results of previously computed segments, significantly reducing redundant calculations and improving efficiency.

Code Solutions

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    memo = {}
    
    def backtrack(start):
        if start in memo:
            return memo[start]
        if start == len(s):
            return [""]

        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for sub_sentence in backtrack(end):
                    if sub_sentence:
                        sentences.append(word + " " + sub_sentence)
                    else:
                        sentences.append(word)

        memo[start] = sentences
        return sentences

    return backtrack(0)

# Example usage
print(wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]))
← Back to All Questions