Sponsored
Sponsored
This approach involves using a Trie data structure to store all words. We then perform a DFS to check if a word can be formed using other words in the trie. The main advantage of using a Trie is that it provides an efficient way to store and look up words simply by traversing nodes based on each character of the word.
We will mark nodes in the Trie that represent the end of a word and during DFS checks if the current segment of the word is in the Trie.
Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The DFS function can make at most m calls for each word.
Space Complexity: O(n * m) for storing the Trie, where n is the number of words and m is the average length of the words.
using System.Collections.Generic;
public class TrieNode {
public TrieNode[] Children = new TrieNode[26];
public bool IsEndOfWord;
}
public class Solution {
public void Insert(TrieNode root, string word) {
var node = root;
foreach (char c in word) {
int index = c - 'a';
if (node.Children[index] == null)
node.Children[index] = new TrieNode();
node = node.Children[index];
}
node.IsEndOfWord = true;
}
public bool Dfs(TrieNode root, string word, int start, int count) {
if (start == word.Length)
return count >= 2;
var node = root;
for (int i = start; i < word.Length; i++) {
int index = word[i] - 'a';
if (node.Children[index] == null)
return false;
node = node.Children[index];
if (node.IsEndOfWord && Dfs(root, word, i + 1, count + 1))
return true;
}
return false;
}
public List<string> FindAllConcatenatedWordsInADict(string[] words) {
TrieNode root = new TrieNode();
foreach (var word in words)
if (!string.IsNullOrEmpty(word))
Insert(root, word);
List<string> result = new List<string>();
foreach (var word in words)
if (Dfs(root, word, 0, 0))
result.Add(word);
return result;
}
public static void Main() {
Solution sol = new Solution();
string[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
List<string> concatenatedWords = sol.FindAllConcatenatedWordsInADict(words);
Console.WriteLine("Concatenated Words:");
foreach (var word in concatenatedWords)
Console.WriteLine(word);
}
}
The C# implementation builds a TrieNode structure to hold words, and uses recursion in the form of DFS to check if combinations of words are present. This takes advantage of a similar logical structure to other language implementations albeit with C# syntax.
In this approach, dynamic programming (DP) is used to efficiently solve the problem of finding concatenated words. The idea is to treat each word as a state and store the results of subproblems to avoid repeated calculations. We iterate over each word and for each segment of the word, check if it can be split into valid sub-words based on previously computed results in the DP array.
This can be visualized as using a DP boolean array where each index represents if the word up to that index can be segmented into valid words in the list. This method is beneficial in reducing the number of redundant calculations.
Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The space used for the dp array and hash table is the main contributor.
Space Complexity: O(n * m) due to hash table entry needs.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5
6// Basic hashing function to create unique IDs for words
7int hashCode(const char* key, int modulo) {
8 unsigned long hash = 5381;
9 int c;
10 while ((c = *key++))
11 hash = ((hash << 5) + hash) + c; // hash * 33 + c
12 return hash % modulo;
13}
14
15// Dynamic Word Dictionary using separate chaining for collision resolution
16typedef struct Node {
17 char* key;
18 struct Node* next;
19} Node;
20
21void insertNode(Node** table, const char* key, int modulo) {
22 int hash = hashCode(key, modulo);
23 Node* newNode = (Node*)malloc(sizeof(Node));
24 newNode->key = strdup(key);
25 newNode->next = table[hash];
26 table[hash] = newNode;
27}
28
29bool searchNode(Node** table, const char* key, int modulo) {
30 int hash = hashCode(key, modulo);
31 Node* node = table[hash];
32 while (node) {
33 if (strcmp(node->key, key) == 0)
34 return true;
35 node = node->next;
36 }
37 return false;
38}
39
40bool isConcatenatedWord(const char* word, Node** table, int modulo) {
41 int len = strlen(word);
42 if (len == 0) return false;
43 bool* dp = (bool*)calloc(len + 1, sizeof(bool));
44 dp[0] = true;
45
46 for (int i = 1; i <= len; i++) {
47 for (int j = 0; j < i; j++) {
48 if (dp[j]) {
49 char* subword = strndup(word + j, i - j);
50 if (searchNode(table, subword, modulo)) {
51 dp[i] = true;
52 free(subword);
53 break;
54 }
55 free(subword);
56 }
57 }
58 }
59
60 bool result = dp[len];
61 free(dp);
62 return result;
63}
64
65char** findAllConcatenatedWords(char** words, int wordsSize, int* returnSize) {
66 const int modulo = 10007;
67 Node** table = (Node**)calloc(modulo, sizeof(Node*));
68
69 for (int i = 0; i < wordsSize; i++) {
70 insertNode(table, words[i], modulo);
71 }
72
73 char** result = (char**)malloc(wordsSize * sizeof(char*));
74 *returnSize = 0;
75
76 for (int i = 0; i < wordsSize; i++) {
77 int len = strlen(words[i]);
78 // Temporarily remove the word from table for accurate concatenation check
79 insertNode(table, "", modulo); // dummy insert
80 if (isConcatenatedWord(words[i], table, modulo)) {
81 result[(*returnSize)++] = words[i];
82 }
83 insertNode(table, words[i], modulo); // Re-insert word
84 }
85
86 // Free the hash table
87 for (int i = 0; i < modulo; i++) {
88 Node* node = table[i];
89 while (node) {
90 Node* tmp = node;
91 node = node->next;
92 free(tmp->key);
93 free(tmp);
94 }
95 }
96 free(table);
97
98 return result;
99}
100
101// Usage example
102int main() {
103 char* words[] = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
104 int wordsSize = sizeof(words) / sizeof(words[0]);
105 int returnSize;
106 char** result = findAllConcatenatedWords(words, wordsSize, &returnSize);
107
108 printf("Concatenated Words: \n");
109 for (int i = 0; i < returnSize; i++) {
110 printf("%s\n", result[i]);
111 }
112
113 return 0;
114}
115The C solution uses a hashed linked list structure to store words and checks if each word is a concatenated word using dynamic programming. A boolean array is used to record which parts of the word can be formed by other words. The solution attempts to hash words into buckets and checks for matches to segment words.