Problem of The Day: Word Break II

Problem Statement

Backtrack Approach - TLE

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        len_s = len(s)
        len_wordDict = len(wordDict)
        word_len_dict = defaultdict(int)
        res = set()
        memo = defaultdict()

        for word in wordDict:
            word_len_dict[word] = len(word)

        def isValid(arr):
            curr_word = ''.join(arr)
            return curr_word == s

        def dfs(index, curr_len, curr):
            if curr_len == len_s:
                if isValid(curr):
                    res.add(' '.join(curr))
                    return

            if index == len_wordDict:
                return

            if curr_len > len_s:
                return

            for j in range(len_wordDict):
                curr_word = wordDict[j]
                if curr_word in s:
                    dfs(j, curr_len + word_len_dict[curr_word], curr + [curr_word])


        dfs(0, 0, [])

        return list(res)

Memoization Approach

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordSet = 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 wordSet:
                    for sentence in backtrack(end):
                        if sentence:
                            sentences.append(word + ' ' + sentence)
                        else:
                            sentences.append(word)

            memo[start] = sentences
            return sentences

        return backtrack(0)

Editorial

Approach 1: Backtracking

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        # Convert wordDict to a set for O(1) lookups
        word_set = set(wordDict)
        results = []
        # Start the backtracking process
        self._backtrack(s, word_set, [], results, 0)
        return results

    def _backtrack(
        self,
        s: str,
        word_set: set,
        current_sentence: List[str],
        results: List[str],
        start_index: int,
    ):
        # If we've reached the end of the string, add the current sentence to results
        if start_index == len(s):
            results.append(" ".join(current_sentence))
            return

        # Iterate over possible end indices
        for end_index in range(start_index + 1, len(s) + 1):
            word = s[start_index:end_index]
            # If the word is in the set, proceed with backtracking
            if word in word_set:
                current_sentence.append(word)
                # Recursively call backtrack with the new end index
                self._backtrack(
                    s, word_set, current_sentence, results, end_index
                )
                # Remove the last word to backtrack
                current_sentence.pop()

• Time: O(2^n)
• Space: O(2^n)

Approach 2: Dynamic Programming - Memoization

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        memoization = {}
        return self._dfs(s, word_set, memoization)

    # Depth-first search function to find all possible word break combinations
    def _dfs(
        self, remaining_str: str, word_set: set, memoization: dict
    ) -> List[str]:
        # Check if result for this substring is already memoized
        if remaining_str in memoization:
            return memoization[remaining_str]
        # Base case: when the string is empty, return a list containing an empty string
        if not remaining_str:
            return [""]
        results = []
        for i in range(1, len(remaining_str) + 1):
            current_word = remaining_str[:i]
            # If the current substring is a valid word
            if current_word in word_set:
                for next_word in self._dfs(
                    remaining_str[i:], word_set, memoization
                ):
                    # Append current word and next word with space in between if next word exists
                    results.append(
                        current_word + (" " if next_word else "") + next_word
                    )
        # Memoize the results for the current substring
        memoization[remaining_str] = results
        return results

Approach 3: Dynamic Programming - Tabulation

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        # Map to store results of subproblems
        dp = {}

        # Iterate from the end of the string to the beginning
        for start_idx in range(len(s), -1, -1):
            # List to store valid sentences starting from start_idx
            valid_sentences = []

            # Iterate from start_idx to the end of the string
            for end_idx in range(start_idx, len(s)):
                # Extract substring from start_idx to end_idx
                current_word = s[start_idx : end_idx + 1]

                # Check if the current substring is a valid word
                if self.is_word_in_dict(current_word, wordDict):
                    # If it's the last word, add it as a valid sentence
                    if end_idx == len(s) - 1:
                        valid_sentences.append(current_word)
                    else:
                        # If it's not the last word, append it to each sentence formed by the remaining substring
                        sentences_from_next_index = dp.get(end_idx + 1, [])
                        for sentence in sentences_from_next_index:
                            valid_sentences.append(
                                current_word + " " + sentence
                            )

            # Store the valid sentences in dp
            dp[start_idx] = valid_sentences

        # Return the sentences formed from the entire string
        return dp.get(0, [])

    # Helper function to check if a word is in the word dictionary
    def is_word_in_dict(self, word: str, word_dict: List[str]) -> bool:
        return word in word_dict