Approach

Word Break

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

Key Insight

This is a Dynamic Programming problem!

For each position i, check if:

Any word in dictionary matches s[j:i]
AND s[0:j] is breakable (dp[j] is true)

dp[i] = true if there exists j where:

dp[j] is true
s[j:i] is in wordDict

Solution 1: Dynamic Programming (Bottom-Up)

Build solution from left to right.

Algorithm:

Create dp array of size n+1
dp[0] = true (empty string)
For each position i from 1 to n:
- For each j from 0 to i:
  - If dp[j] and s[j:i] in wordDict:
    - dp[i] = true
Return dp[n]

Solution 2: BFS Approach

Treat as graph traversal.

Algorithm:

Use queue starting from index 0
For each position:
- Try all possible words from this position
- If word matches, add end position to queue
Return true if we reach end of string

Solution 3: DFS with Memoization

Top-down approach with caching.

Algorithm:

Use memoization to avoid recomputing
For each position:
- Try all possible words
- Recursively check remaining string
Cache results for each position

Complexity Analysis

DP Solution:

Time Complexity: O(n² × m) where n = s.length, m = avg word length
- For each position, check all previous positions
- Each check involves substring comparison
Space Complexity: O(n) - DP array

BFS/DFS:

Time Complexity: O(n² × m)
Space Complexity: O(n) - queue/stack + memo

Pattern Recognition

This problem demonstrates:

Dynamic Programming with string segmentation
BFS/DFS alternative approaches
Memoization optimization
Substring matching pattern
Foundation for Word Break II

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Dynamic Programming (Bottom-Up)
5    public boolean wordBreak(String s, List<String> wordDict) {
6        int n = s.length();
7        Set<String> wordSet = new HashSet<>(wordDict);
8        boolean[] dp = new boolean[n + 1];
9        dp[0] = true;  // Empty string
10
11        for (int i = 1; i <= n; i++) {
12            for (int j = 0; j < i; j++) {
13                // If s[0:j] is breakable AND s[j:i] is a word
14                if (dp[j] && wordSet.contains(s.substring(j, i))) {
15                    dp[i] = true;
16                    break;  // Found valid segmentation
17                }
18            }
19        }
20
21        return dp[n];
22    }
23
24    // Solution 2: BFS Approach
25    public boolean wordBreakBFS(String s, List<String> wordDict) {
26        Set<String> wordSet = new HashSet<>(wordDict);
27        Queue<Integer> queue = new LinkedList<>();
28        Set<Integer> visited = new HashSet<>();
29        queue.offer(0);
30        visited.add(0);
31
32        while (!queue.isEmpty()) {
33            int start = queue.poll();
34
35            // Try all possible words from this position
36            for (int end = start + 1; end <= s.length(); end++) {
37                if (visited.contains(end)) {
38                    continue;
39                }
40
41                // If substring is a word
42                if (wordSet.contains(s.substring(start, end))) {
43                    if (end == s.length()) {
44                        return true;
45                    }
46                    queue.offer(end);
47                    visited.add(end);
48                }
49            }
50        }
51
52        return false;
53    }
54
55    // Solution 3: DFS with Memoization
56    public boolean wordBreakMemo(String s, List<String> wordDict) {
57        Set<String> wordSet = new HashSet<>(wordDict);
58        Map<Integer, Boolean> memo = new HashMap<>();
59        return dfs(s, 0, wordSet, memo);
60    }
61
62    private boolean dfs(String s, int start, Set<String> wordSet,
63                       Map<Integer, Boolean> memo) {
64        // Base case: reached end
65        if (start == s.length()) {
66            return true;
67        }
68
69        // Check memo
70        if (memo.containsKey(start)) {
71            return memo.get(start);
72        }
73
74        // Try all possible words from this position
75        for (int end = start + 1; end <= s.length(); end++) {
76            String word = s.substring(start, end);
77            if (wordSet.contains(word) && dfs(s, end, wordSet, memo)) {
78                memo.put(start, true);
79                return true;
80            }
81        }
82
83        memo.put(start, false);
84        return false;
85    }
86
87    // Solution 4: Optimized DP
88    public boolean wordBreakOptimized(String s, List<String> wordDict) {
89        Set<String> wordSet = new HashSet<>(wordDict);
90        int maxLen = 0;
91        for (String word : wordDict) {
92            maxLen = Math.max(maxLen, word.length());
93        }
94
95        int n = s.length();
96        boolean[] dp = new boolean[n + 1];
97        dp[0] = true;
98
99        for (int i = 1; i <= n; i++) {
100            // Only check words up to maxLen
101            for (int j = Math.max(0, i - maxLen); j < i; j++) {
102                if (dp[j] && wordSet.contains(s.substring(j, i))) {
103                    dp[i] = true;
104                    break;
105                }
106            }
107        }
108
109        return dp[n];
110    }
111}
112