Problem Description
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.
Key Insights
- The problem can be solved using dynamic programming.
- A boolean array can be used to track which prefixes of the string can be segmented.
- Each segment can be checked against the dictionary to determine if it forms a valid word.
Space and Time Complexity
Time Complexity: O(n^2 * m), where n is the length of the string s and m is the number of words in wordDict.
Space Complexity: O(n), for the boolean array used to track segmentations.
Solution
The solution employs dynamic programming to check if the string can be segmented into valid words found in wordDict. We maintain a boolean array dp where dp[i] indicates whether the substring s[0:i] can be segmented using words from wordDict. For each position i, we check all previous positions j to see if s[j:i] is in the dictionary and if dp[j] is true. If both conditions are met, we set dp[i] to true.