Dynamic Programming is a common approach for problems involving finding solutions over mutable subsets of an input set. We can use a boolean array 'dp' with length 'n+1', where 'n' is the length of the input string 's'. 'dp[i]' will indicate whether the substring 's[0...i-1]' can be segmented into words from the dictionary. We initialize 'dp[0]' to true since an empty substring can always be segmented.
For each position 'i' from 1 to n, iterate through each previous position 'j' from 0 to i-1, and check if the substring 's[j:i]' is in the word dictionary and if 'dp[j]' is true. If both conditions are met, set 'dp[i]' to true and break out of the loop.
The final answer will be found in 'dp[n]'.
Time Complexity: O(n^2 * m), where n is the length of the string and m is the size of the dictionary. Each substring check requires a loop over the dictionary.
Space Complexity: O(n) for the dp array.
1import java.util.*;
2
3public class Solution {
4 public boolean wordBreak(String s, List<String> wordDict) {
5 Set<String> dict = new HashSet<>(wordDict);
6 boolean[] dp = new boolean[s.length() + 1];
7 dp[0] = true;
8
9 for (int i = 1; i <= s.length(); i++) {
10 for (int j = 0; j < i; j++) {
11 if (dp[j] && dict.contains(s.substring(j, i))) {
12 dp[i] = true;
13 break;
14 }
15 }
16 }
17 return dp[s.length()];
18 }
19}This Java solution uses a HashSet to store dictionary words. Using a similar DP approach, we iterate and check each substring of 's'. If the substring exists in the dictionary and prior fragments are valid (based on dp[j]), update dp[i] to true.
This approach utilizes Depth First Search (DFS) with the help of memoization to avoid redundant work. By storing the results of overlaps in a memoization structure, we cut down unnecessary recalculations. The recursive function attempts to segment the string from an index 'start' and uses a hash set for quick lookups of dictionary words. The function operates recursively trying to partition the string and caches results for indices already computed, preventing repetitions of partial solutions.
Time Complexity: O(n^2) in the worst case due to substring check overhead between start and end.
Space Complexity: O(n) for the memo array storage.
1import java.util.*;
2
3public class Solution {
4 private Map<Integer, Boolean> memo = new HashMap<>();
5
6 public boolean wordBreak(String s, List<String> wordDict) {
7 return dfs(s, new HashSet<>(wordDict), 0);
8 }
9
10 private boolean dfs(String s, Set<String> wordDict, int start) {
11 if (start == s.length()) return true;
12 if (memo.containsKey(start)) return memo.get(start);
13
14 for (int end = start + 1; end <= s.length(); end++) {
15 if (wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end)) {
16 memo.put(start, true);
17 return true;
18 }
19 }
20 memo.put(start, false);
21 return false;
22 }
23}This Java solution involves a DFS approach with memoization stored in a HashMap. It recursively processes substrings from the start index, storing results to avoid recomputation.