Word Break — Java Coding Problem
Difficulty: hard | Category: dynamic-programming
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. Hint: Bottom-up DP — `dp[i]` is `true` if the substring `s[0..i]` can be segmented. For each `i`, check all `j < i` where `dp[j]` is true and `s[j..i]` is in the dictionary.
Examples
Example 1
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" → "leet" + "code".
Example 2
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "applepenapple" → "apple" + "pen" + "apple". Reuse is allowed.
Example 3
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false