Obsidian Notes

10. Word Break

5 min read

Description

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.

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 <= 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.

Approach

  • Create array with first of out of bounds index set as true
  • Loop through the string length and then loop through the dictionary and check if substring matches
  • If everything works then true will be set as true by the end of the loop
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] d = new boolean[s.length() + 1];
        d[s.length()] = true;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (String w: wordDict) {
                if (i + w.length() <= s.length() && 
                    s.substring(i, i + w.length()).equals(w)) {
                        d[i] = d[i + w.length()];
                }
                if (d[i]) break;
 
            }
        }
        return d[0];
    }
}

Primary Approach: 1D Dynamic Programming ( Time, Space)

Intuition

Define dp[i] as a boolean value indicating whether the prefix s[0 ... i-1] can be segmented into a valid sequence of dictionary words:

  1. Base Case: dp[0] = true because an empty string can always be segmented.
  2. Set & Max Word Length Optimization: Convert wordDict to a HashSet for average lookup time. Store the maximum length of any word in wordDict (maxLen) to avoid checking substrings longer than the longest word in the dictionary.
  3. Transition: For each ending position i from to , check all possible starting positions j from to :
    • If dp[j] is true AND wordSet.contains(s.substring(j, i)), set dp[i] = true and break early out of the inner loop.
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>();
        int maxLen = 0;
 
        for (String word : wordDict) {
            wordSet.add(word);
            maxLen = Math.max(maxLen, word.length());
        }
 
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // Base case: empty prefix is valid
 
        for (int i = 1; i <= n; i++) {
            // Only look back up to maxLen characters
            for (int j = i - 1; j >= Math.max(0, i - maxLen); j--) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // Move to next position once a valid split is found
                }
            }
        }
 
        return dp[n];
    }
}

Complexity

  • Time Complexity: — Where is the length of s and is the maximum word length in wordDict. The inner loop runs at most times, and string slicing (substring) takes time.
  • Space Complexity: — for the dp array plus to store dictionary words of max length inside the HashSet.

Alternative Approach: Breadth-First Search (BFS) ( Time, Space)

Intuition

Treat the string indices as nodes in a graph, where a directed edge exists from index start to index end if s.substring(start, end) is present in wordDict:

  1. Maintain a Queue<Integer> containing starting index 0.
  2. Use a boolean[] visited array to prevent re-visiting the same start index multiple times.
  3. For each popped start index, iterate through end positions end from start + 1 to min(N, start + maxLen).
  4. If s.substring(start, end) exists in the dictionary and !visited[end]:
    • If end == N, return true (reached the end of the string).
    • Mark visited[end] = true and push end to the queue.
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
 
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
 
        int n = s.length();
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new ArrayDeque<>();
 
        queue.add(0);
        visited[0] = true;
 
        while (!queue.isEmpty()) {
            int start = queue.poll();
 
            for (int end = start + 1; end <= Math.min(n, start + maxLen); end++) {
                if (visited[end]) continue;
 
                if (wordSet.contains(s.substring(start, end))) {
                    if (end == n) return true;
                    visited[end] = true;
                    queue.add(end);
                }
            }
        }
 
        return false;
    }
}

Complexity

  • Time Complexity: — Each index enters the queue at most once.
  • Space Complexity: — Space for queue, visited array, and dictionary hash set.

Key Interview Discussion Points

  • Trie Alternative: A Trie can be constructed from wordDict to perform prefix lookups character-by-character instead of calling s.substring(), reducing substring creation overhead.
  • Importance of maxLen Optimization: Unoptimized inner loops iterate from to , causing iterations. Limiting lookbacks to reduces runtime significantly when dictionary word lengths are bounded.

Easy Memory Rule

“dp[i] is valid IF dp[j] was valid AND s.substring(j, i) is in wordDict!”

Backlinks