Word Break Solution for Amazon
Company: Amazon · Difficulty: Hard · Topics: String, Dynamic Programming, Hash Table, Trie
Problem Statement
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.
Examples
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".
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: "catsandog" cannot be segmented into dictionary words.
Example 4:
Input: s = "aaaaaaa", wordDict = ["aaaa","aaa"]
Output: true
Explanation: "aaaaaaa" can be segmented as "aaaa aaa" or "aaa aaaa".
Intuition
The key insight is to use dynamic programming to check if the string can be broken down into valid words. We can use a DP array where dp[i] represents whether the substring s[0...i-1] can be segmented.
Approach
Approach 1: Dynamic Programming (Optimal)
1. Create a DP array where dp[i] = true if s[0...i-1] can be segmented
2. For each position i, check all possible word endings
3. If a word ending at i is in the dictionary and dp[start] is true, set dp[i] = true
4. Return dp[n] where n is the length of the string
Approach 2: Dynamic Programming with Hash Set
1. Convert wordDict to a hash set for O(1) lookup
2. Same DP logic but with hash set optimization
3. More efficient for large dictionaries
Approach 3: Recursive with Memoization
1. Use recursion to try all possible word combinations
2. Use memoization to avoid redundant calculations
3. Less efficient than iterative DP
Dry Run
Let's trace through Example 1: s = "leetcode", wordDict = ["leet","code"]
Dynamic Programming Approach:
- dp[0] = true (empty string)
- dp[1] = false (no word ending at index 1)
- dp[2] = false (no word ending at index 2)
- dp[3] = false (no word ending at index 3)
- dp[4] = true (word "leet" ending at index 4, dp[0] = true)
- dp[5] = false (no word ending at index 5)
- dp[6] = false (no word ending at index 6)
- dp[7] = false (no word ending at index 7)
- dp[8] = true (word "code" ending at index 8, dp[4] = true)
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Dynamic Programming (Optimal)
Time Complexity: O(n² * m) - n is string length, m is max word length
Space Complexity: O(n) - DP array
Solution 2: Dynamic Programming with Hash Set
Time Complexity: O(n² * m) - n is string length, m is max word length
Space Complexity: O(n + k) - DP array + hash set
Solution 3: Recursive with Memoization
Time Complexity: O(n² * m) - n is string length, m is max word length
Space Complexity: O(n) - Recursion stack + memoization