{x}
blog image

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

 

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

 

Constraints:

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.
  • Input is generated in a way that the length of the answer doesn't exceed 105.

Solution Explanation for Word Break II

This problem asks to find all possible ways to break a given string s into words from a dictionary wordDict, where each word is a valid word from the dictionary. The solution uses a Trie data structure for efficient word lookup and a depth-first search (DFS) algorithm to explore all possible sentence constructions.

Approach

  1. Trie Construction: A Trie is built from the words in wordDict. A Trie is a tree-like data structure that allows for efficient prefix searching. Each node in the Trie represents a character, and paths from the root to a leaf node represent words in the dictionary. This allows for fast checking if a prefix of s is a valid word.

  2. Depth-First Search (DFS): A recursive DFS function explores all possible ways to break the string. It starts from the beginning of the string and iterates through possible word lengths. For each length, it checks if the substring of that length is a valid word (using the Trie).

    • Base Case: If the remaining string is empty (s is completely broken down into words), a sentence is found, and it's added to the result.

    • Recursive Step: If a valid word is found, the DFS function recursively calls itself on the remaining substring. This continues until the entire string is processed or no valid word is found for a given prefix.

  3. Result Construction: The DFS function returns a list of lists. Each inner list represents a sentence, with each element being a word. Finally, these lists are converted into strings, each string being a sentence with spaces between words.

Time Complexity Analysis

  • Trie Construction: Building the Trie takes O(M), where M is the total number of characters in all words in wordDict.

  • DFS: In the worst case, the DFS function might explore all possible ways to partition the string. The number of possible partitions is exponential with respect to the length of the string, N. Each partition check takes O(1) time (constant time) due to the efficient Trie lookup. Thus, the time complexity of the DFS is O(2N) in the worst case, though it's usually much less than that in practice.

  • Overall: The overall time complexity is dominated by the DFS and is, therefore, O(2N) in the worst case.

Space Complexity Analysis

  • Trie: The space complexity of the Trie is O(M).

  • DFS: The space complexity of the DFS is determined by the recursion depth and the size of the intermediate results. The recursion depth can be at most N (length of s), and each sentence can have at most N words. Therefore, the space complexity of the DFS is O(N2) in the worst case.

  • Overall: The overall space complexity is dominated by the DFS and the Trie, resulting in O(N2 + M) in the worst case.

Code Examples (Python, Java, Go, C#)

The code examples provided earlier demonstrate the implementation of this approach in different programming languages. Each example follows the same algorithmic steps: Trie construction, DFS, and result generation. The choice of language mainly affects the syntax and data structure implementations.