Skip to content
AI360Xpert
Back to 1-D Dynamic Programming
Medium

Word Break

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

Input:s = "applepen", wordDict = ["apple","pen"]
Output:true
Return true because "applepen" can be segmented as "apple pen".
Input:s = "applepenapple", wordDict = ["apple","pen"]
Output:true
Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.
Input:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output:false
There is no valid segmentation.

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Dynamic Programming

Approach

We can use a DP array `dp` of size `n + 1` where `dp[i]` is true if the substring `s[0...i-1]` can be segmented into dictionary words. We initialize `dp[0] = true` (an empty string is valid). Then we iterate `i` from 1 to `s.length`. For each `i`, we check if there is any `j` (from 0 to `i-1`) such that `dp[j]` is true AND the substring `s[j...i-1]` is in the dictionary. If we find such a `j`, we set `dp[i] = true` and break (no need to check further for this `i`).

Complexity Analysis

Time Complexity
O(n * m * L)
Space Complexity
O(n)

n is the length of the string, m is the number of words in the dictionary, and L is the maximum length of a word. At each index, we check against words in the dictionary and string comparison takes O(L) time. Space complexity is O(n) for the DP array.

Solution.java
class Solution {    public boolean wordBreak(String s, List<String> wordDict) {        Set<String> wordSet = new HashSet<>(wordDict);        int n = s.length();        boolean[] dp = new boolean[n + 1];        dp[0] = true;                for (int i = 1; i <= n; i++) {            // Optimization: check words from dictionary directly instead of nested loop            for (String word : wordDict) {                int len = word.length();                if (i >= len && dp[i - len] && s.substring(i - len, i).equals(word)) {                    dp[i] = true;                    break;                }            }        }                return dp[n];    }}