Word Break
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.
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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare unique.
Solve it on LeetCode
Approaches
1. Recursion
Intuition:
In this approach, we will use recursion to break down the problem. The idea is to check if the current prefix of the string can be found in the word dictionary, and if it is, we recursively check the remaining substring. If any path returns true, we know the string can be segmented according to the dictionary.
This method may have overlapping subproblems, which makes it inefficient for larger inputs.
Code:
- Time Complexity: O(2^n) where n is the length of the string
sdue to the exponential growth in possible substrings. - Space Complexity: O(n) for the recursion stack (depth of the recursion tree).
2. Recursion with Memoization
Intuition:
To optimize the previous recursive solution, we store the result of already processed substrings in a memoization table to avoid recomputation. This approach utilizes dynamic programming concepts to store results of subproblems, thus reducing redundant calculations.
Code:
- Time Complexity: O(n^2) for each substring and position due to memoization.
- Space Complexity: O(n) for the memoization table.
3. Dynamic Programming
Intuition:
We can further improve the solution by using dynamic programming. The idea is to use a boolean dp array where dp[i] represents whether the substring s[0...i] can be segmented using the dictionary. For each position, we check all possible partitions, updating the dp array based on previously computed results.
Code:
- Time Complexity: O(n^3) because of the two nested loops and substring check, but efficiently optimized by using a set.
- Space Complexity: O(n) for the dp array.