{x}
blog image

Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

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

 

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Solution Explanation for Word Break

The problem asks whether a given string s can be segmented into a space-separated sequence of one or more words from a dictionary wordDict. We can solve this using dynamic programming or a Trie-based approach. Both approaches are detailed below.

Approach 1: Dynamic Programming

This approach uses a boolean array f where f[i] is true if the substring s[0:i] can be segmented into words from the dictionary, and false otherwise.

Algorithm:

  1. Initialization: Create a boolean array f of size n+1 (where n is the length of s), initialized with f[0] = True (an empty string can always be segmented) and f[i] = False for i > 0.

  2. Iteration: Iterate through the string s from index 1 to n. For each index i, check if the substring s[j:i] (where 0 <= j < i) is in the dictionary wordDict and if f[j] is true. If both conditions are met, it means the substring s[0:i] can be segmented, so set f[i] = True.

  3. Result: f[n] will indicate whether the entire string s can be segmented.

Time Complexity: O(n*m), where n is the length of the string and m is the length of the dictionary. The nested loops iterate through all possible substrings and check if they exist in the dictionary.

Space Complexity: O(n), for the boolean array f.

Approach 2: Trie

This approach uses a Trie data structure to efficiently search for words in the dictionary.

Algorithm:

  1. Trie Construction: Construct a Trie from the words in wordDict.

  2. Dynamic Programming with Trie: Similar to Approach 1, we use a boolean array f. However, instead of checking wordDict directly for each substring, we traverse the Trie. If a substring matches a word in the Trie (indicated by isEnd flag) and f[j] is true, then f[i] is set to true.

  3. Result: Same as Approach 1, f[n] indicates the final result.

Time Complexity: The Trie construction is O(M), where M is the sum of lengths of all words in wordDict. The dynamic programming part is still O(n^2) in the worst case because of the nested loops. However, Trie lookups are significantly faster than iterating through the whole dictionary, leading to improved performance over large datasets.

Space Complexity: O(M) for the Trie and O(n) for the boolean array f.

The provided code examples in multiple programming languages implement both approaches. Choose the approach that best suits your needs based on the expected size of the input string and dictionary. For smaller inputs, the difference in performance between these two approaches is not significant. However, for larger inputs, the Trie-based approach tends to perform better due to the efficient lookups.