This problem is a classic example of dynamic programming involving string segmentation. The goal is to determine whether a given string can be split into valid words from a dictionary.

The task requires us to check if the string s can be segmented into a space-separated sequence of one or more dictionary words provided in wordDict.

Intuition:

The central idea revolves around dynamic programming. We try to break the string into smaller substrings and check whether each part exists in the dictionary. If we can build the entire string step-by-step using valid words, then segmentation is possible.

We use a DP array where dp[i] represents whether the substring s[0...i-1] can be segmented into valid dictionary words.

Step-by-step thinking:

Convert Dictionary to Set: Store all words from wordDict in a Set for fast lookup (O(1)).
Initialize DP Array: Create a boolean array dp of size n + 1, where n is the length of the string. Set dp[0] = true since an empty string is always valid.
Iterate Through String: For each index i from 1 to n, check all possible partitions.
Check All Partitions: For each j from 0 to i-1, check if:
- dp[j] is true (left part is valid)
- s.substring(j, i) exists in the dictionary
Update DP: If both conditions are satisfied, mark dp[i] = true and break early since we found a valid split.
Return Result: Finally, return dp[n], which tells whether the entire string can be segmented.

Time Complexity: O(n²), due to checking all substrings.
Space Complexity: O(n), for the DP array.
Learn Complexity

140. Word Break

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases