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 <stdbool.h>
2#include <string.h>
3
4bool wordBreak(char * s, char ** wordDict, int wordDictSize) {
5 int n = strlen(s);
6 bool dp[n + 1];
7 memset(dp, false, sizeof(dp));
8 dp[0] = true;
9
10 for (int i = 1; i <= n; i++) {
11 for (int j = 0; j < i; j++) {
12 if (dp[j] && validSubstring(s + j, i - j, wordDict, wordDictSize)) {
13 dp[i] = true;
14 break;
15 }
16 }
17 }
18
19 return dp[n];
20}
21
22bool validSubstring(char* start, int len, char ** wordDict, int wordDictSize) {
23 for (int k = 0; k < wordDictSize; k++) {
24 if (strncmp(start, wordDict[k], len) == 0 && strlen(wordDict[k]) == len) {
25 return true;
26 }
27 }
28 return false;
29}This C solution involves two key functions: 'wordBreak' and 'validSubstring'. We first initialize a DP array of size n+1 and set dp[0] to true. For every substring of s (from j to i), we check if it exists in the dictionary using 'validSubstring'. If an entry exists and dp[j] is true, we set dp[i] to true. The function ends by returning dp[n], which indicates the segmental validity of the entire string.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private Dictionary<int, bool> memo = new Dictionary<int, bool>();
6
7 public bool WordBreak(string s, IList<string> wordDict) {
8 HashSet<string> wordSet = new HashSet<string>(wordDict);
9 return Dfs(s, wordSet, 0);
10 }
11
12 private bool Dfs(string s, HashSet<string> wordDict, int start) {
13 if (start == s.Length) return true;
14 if (memo.ContainsKey(start)) return memo[start];
15
16 for (int end = start + 1; end <= s.Length; end++) {
17 if (wordDict.Contains(s.Substring(start, end - start)) && Dfs(s, wordDict, end)) {
18 memo[start] = true;
19 return true;
20 }
21 }
22 memo[start] = false;
23 return false;
24 }
25}This C# solution follows the recursive memoization method, leveraging a dictionary to store the solution state, avoiding redundant computations via memoization.