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.
1#include <vector>
2#include <string>
3#include <unordered_set>
4
5using namespace std;
6
7bool wordBreak(string s, vector<string>& wordDict) {
8 unordered_set<string> dict(wordDict.begin(), wordDict.end());
9 vector<bool> dp(s.size() + 1, false);
10 dp[0] = true;
11
12 for (int i = 1; i <= s.size(); ++i) {
13 for (int j = 0; j < i; ++j) {
14 if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
15 dp[i] = true;
16 break;
17 }
18 }
19 }
20 return dp[s.size()];
21}The C++ solution leverages an unordered_set for quick dictionary lookup. We iterate through substrings of 's', checking each substring against the dictionary and verifying with our dp array. This allows efficient segmentation check.
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.
1#include <stdbool.h>
2#include <string.h>
3
4bool wordBreakUtil(char* s, int start, char** wordDict, int wordDictSize, int* memo) {
5 if (start == strlen(s)) return true;
6 if (memo[start] != -1) return memo[start];
7
8 for (int end = start + 1; end <= strlen(s); end++) {
9 if (isInDict(s + start, end - start, wordDict, wordDictSize) && wordBreakUtil(s, end, wordDict, wordDictSize, memo)) {
10 return memo[start] = true;
11 }
12 }
13
14 return memo[start] = false;
15}
16
17bool isInDict(char* start, int len, char** wordDict, int wordDictSize) {
18 for (int i = 0; i < wordDictSize; i++) {
19 if (strncmp(start, wordDict[i], len) == 0 && strlen(wordDict[i]) == len) {
20 return true;
21 }
22 }
23 return false;
24}
25
26 bool wordBreak(char* s, char** wordDict, int wordDictSize) {
27 int n = strlen(s);
28 int memo[n];
29 memset(memo, -1, sizeof(memo));
30 return wordBreakUtil(s, 0, wordDict, wordDictSize, memo);
31}This C solution uses a helper function 'wordBreakUtil' which applies DFS recursively with memoization to store results of overlapping subproblems. The main function initializes a memoization array and calls the utility function for processing.