Sponsored
Sponsored
This approach utilizes recursion to explore all possible partitions of the string, while memoization stores the results of subproblems to avoid redundant computations. We start from the first character, continuously check substrings against the dictionary, and recursively process the remaining parts of the string. The solutions for these parts are combined to form complete sentences. Memoization optimizes this by caching results of repeating subproblems.
Time Complexity: O(n^3), where n is the length of the input string, due to substring operations and memoization.
Space Complexity: O(n^3), for memoization of results and recursion stack.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4#include <stdbool.h>
5
6// Define a linked list for storing the results
7typedef struct ListNode {
8 char* val;
9 struct ListNode* next;
10} ListNode;
11
12typedef struct {
13 ListNode** data;
14 char** words;
15 int size;
16} Memo;
17
18Memo* initMemo(int size) {
19 Memo* memo = malloc(sizeof(Memo));
20 memo->data = malloc(sizeof(ListNode*) * size);
21 memset(memo->data, 0, sizeof(ListNode*) * size);
22 memo->words = malloc(sizeof(char*) * size);
23 for (int i = 0; i < size; i++) {
24 memo->words[i] = NULL;
25 }
26 memo->size = size;
27 return memo;
28}
29
30void freeMemo(Memo* memo) {
31 for (int i = 0; i < memo->size; i++) {
32 ListNode* node = memo->data[i];
33 while (node) {
34 ListNode* temp = node;
35 node = node->next;
36 free(temp->val);
37 free(temp);
38 }
39 }
40 free(memo->data);
41 free(memo->words);
42 free(memo);
43}
44
45ListNode* appendString(ListNode* list, const char* word) {
46 ListNode* newNode = malloc(sizeof(ListNode));
47 newNode->val = strdup(word);
48 newNode->next = list;
49 return newNode;
50}
51
52bool findWord(const char* word, char** wordDict, int wordCount) {
53 for (int i = 0; i < wordCount; ++i) {
54 if (strcmp(word, wordDict[i]) == 0) {
55 return true;
56 }
57 }
58 return false;
59}
60
61ListNode* backtrack(const char* s, int start, char** wordDict, int wordCount, Memo* memo) {
62 if (memo->data[start] != NULL) return memo->data[start];
63
64 if (start == strlen(s)) {
65 return appendString(NULL, "");
66 }
67
68 ListNode* result = NULL;
69 for (int end = start + 1; end <= strlen(s); ++end) {
70 char* subString = strndup(s + start, end - start);
71 if (findWord(subString, wordDict, wordCount)) {
72 ListNode* subList = backtrack(s, end, wordDict, wordCount, memo);
73 for (ListNode* node = subList; node != NULL; node = node->next) {
74 char* sentence = node->val[0] ? malloc(strlen(subString) + 1 + strlen(node->val) + 1) : strdup(subString);
75 if (node->val[0]) sprintf(sentence, "%s %s", subString, node->val);
76 result = appendString(result, sentence);
77 free(sentence);
78 }
79 }
80 free(subString);
81 }
82
83 memo->data[start] = result;
84 return result;
85}
86
87char** wordBreak(char* s, char** wordDict, int wordCount, int* returnSize) {
88 Memo* memo = initMemo(strlen(s) + 1);
89 ListNode* list = backtrack(s, 0, wordDict, wordCount, memo);
90
91 // Calculate returnSize and prepare return array
92 ListNode* temp = list;
93 *returnSize = 0;
94 while (temp) {
95 (*returnSize)++;
96 temp = temp->next;
97 }
98
99 char** result = malloc(sizeof(char*) * (*returnSize));
100 temp = list;
101 for (int i = 0; i < *returnSize; ++i) {
102 result[i] = strdup(temp->val);
103 temp = temp->next;
104 }
105
106 freeMemo(memo);
107 return result;
108}
109
110#include <stdbool.h>
111
112// Example Usage
113int main() {
114 char* s = "catsanddog";
115 char* wordDict[] = { "cat", "cats", "and", "sand", "dog" };
116 int wordCount = 5;
117 int returnSize = 0;
118 char** sentences = wordBreak(s, wordDict, wordCount, &returnSize);
119 for (int i = 0; i < returnSize; i++) {
120 printf("%s\n", sentences[i]);
121 free(sentences[i]);
122 }
123 free(sentences);
124 return 0;
125}The C solution employs a recursive function, backtrack, that forms valid sentences by appending words found in the dictionary. A linked list stores intermediate results to allow for dynamic sentence construction. Memo is used to cache the processed subproblems to reduce redundant calculations, effectively optimizing the recursive approach.
This method uses dynamic programming to dynamically determine all possible sentences from the string based on the dictionary. We iterate through the string and for each suffix, if a word ends at the current position, all sentences that lead up to this word are combined with the word to form new valid sentences. A 2D list keeps track of sentences possible up to each character index.
Time Complexity: O(n^3), because of substring operations and iteration over previous results.
Space Complexity: O(n^3), for the storage of all potential sentences in a 2D list.
1import java.util.*;
2
3
The Java solution uses a list of lists dp where dp[i] holds all possible sentences that can be formed up to index i. By iterating over every substring, sentences are built incrementally and stored up to each index. Each word ending at index i is checked, and if valid, sentences are built by appending the word to sentences from the previous indexes.