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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <stdbool.h>
5
6#define ALPHABET_SIZE 26
7
8// Trie Node structure
9typedef struct TrieNode {
10 struct TrieNode* children[ALPHABET_SIZE];
11 bool isEndOfWord;
12} TrieNode;
13
14// Function to create a new Trie Node
15TrieNode* createNode() {
16 TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
17 node->isEndOfWord = false;
18 for (int i = 0; i < ALPHABET_SIZE; i++)
19 node->children[i] = NULL;
20 return node;
21}
22
23// Function to insert a word into the Trie
24void insert(TrieNode* root, const char* key) {
25 TrieNode* pCrawl = root;
26 while (*key) {
27 int index = *key - 'a';
28 if (!pCrawl->children[index])
29 pCrawl->children[index] = createNode();
30 pCrawl = pCrawl->children[index];
31 key++;
32 }
33 pCrawl->isEndOfWord = true;
34}
35
36// Helper function to determine if a word can be formed by other words
37bool dfs(TrieNode* root, const char* word, int count) {
38 if (*word == '\0')
39 return count > 1;
40
41 TrieNode* pCrawl = root;
42
43 for (int i = 0; word[i]; i++) {
44 int index = word[i] - 'a';
45 if (pCrawl->children[index] == NULL)
46 return false;
47 pCrawl = pCrawl->children[index];
48
49 if (pCrawl->isEndOfWord) {
50 if (dfs(root, word + i + 1, count + 1))
51 return true;
52 }
53 }
54
55 return false;
56}
57
58// Function to find all concatenated words
59char** findAllConcatenatedWords(char** words, int wordsSize, int* returnSize) {
60 TrieNode* root = createNode();
61 for (int i = 0; i < wordsSize; i++) {
62 if (strlen(words[i]) > 0)
63 insert(root, words[i]);
64 }
65
66 char** result = (char**)malloc(wordsSize * sizeof(char*));
67 *returnSize = 0;
68
69 for (int i = 0; i < wordsSize; i++) {
70 if (dfs(root, words[i], 0)) {
71 result[(*returnSize)++] = words[i];
72 }
73 }
74
75 return result;
76}
77
78// Usage example
79int main() {
80 char* words[] = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
81 int wordsSize = sizeof(words) / sizeof(words[0]);
82 int returnSize;
83 char** result = findAllConcatenatedWords(words, wordsSize, &returnSize);
84
85 printf("Concatenated Words: \n");
86 for (int i = 0; i < returnSize; i++) {
87 printf("%s\n", result[i]);
88 }
89
90 return 0;
91}
92In the C solution, we create a Trie with nodes for each letter and a boolean flag indicating the end of a word. We add all the words into the Trie and then use a depth-first search (DFS) function to check if a given word can be constructed by concatenating other words in the Trie. If it can be constructed, it is added to the results list.
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.
using System.Collections.Generic;
public class Solution {
public List<string> FindAllConcatenatedWordsInADict(string[] words) {
HashSet<string> dict = new HashSet<string>(words);
List<string> result = new List<string>();
foreach (var word in words) {
if (IsConcatenatedWord(word, dict)) {
result.Add(word);
}
}
return result;
}
private bool IsConcatenatedWord(string word, HashSet<string> dict) {
int n = word.Length;
if (n == 0) return false;
bool[] dp = new bool[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.Contains(word.Substring(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void Main(string[] args) {
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);
}
}
In the C# solution, the use of HashSet increases lookup speeds when determining potential word concatenations. With a Boolean DP array that records feasible concatenations leading to the last index, it carefully negotiates an efficient path through each character with continued internal validation through pre-processing.