472. Concatenated Words - Analysis
Concatenated Words \nGiven a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.\nA conca
<h2>Concatenated Words</h2>\nGiven a list of words (<b>without duplicates</b>), please write a program that returns all concatenated words in the given list of words.\nA concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.\n\n**Example**\n<pre><strong>Input:</strong> ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]\n<strong>Output: </strong>["catsdogcats","dogcatsdog","ratcatdogcat"]\n<strong>Explanation: </strong> "catsdogcats" can be concatenated by "cats", "dog" and "cats"; \n "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; \n"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".\n</pre>\n\n<h2 id="solution">Solution</h2>\n<hr>\n<h4>Approach 1: Dynamic Programming</h4>\n<strong>Intuition and Algorithm</strong>\n<p>\nA concatenated word  must be formed by 2 or more shorter words. We will iterate through each word and see if this is a <code>concatenated word</code>.\n</p>\n<p>\nLet\'s try for a dynamic programming (DP) solution.\nGiven the input\n\n<code>Words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]</code>\nWe are going to check, for example, if the word <code>W = ratcatdogcat</code>  is concatenated.\nGiven a prefix of size <code>K</code> of the word <code>W</code>, <code>dp[k]</code> returns a boolean if this prefix can be formed by other words in the dictionary. We have:\n</p>\n\n* <code>dp[0] = True,</code> (empy string) base case\n* <code>dp[1] = False,</code> prefix <code>"r"  </code> is not formed by other words \n* <code>dp[2] = False,</code> prefix <code>"ra"  </code> is not formed by other words\n* <code>dp[3] = True,</code> prefix <code>"rat" </code> exists in W (dictionary)\n* <code>dp[4] = False,</code> prefix <code>"ratc" </code> is not formed by other words\n* <code>dp[5] = False,</code> prefix <code>"ratca"  </code> is not formed by other words \n* <code>dp[6] = False,</code> prefix <code>"ratcat"  </code> Its formed by 2 words in W <code>rat + cat</code>\n* <code>dp[7] = dp[8] =False,</code> \n* <code>dp[9] = True,</code> prefix <code>"ratcatdog"  </code> Its formed by 3 words in W <code>rat + cat +dog</code>\n* <code>dp[10] = dp[11] =False,</code> \n* <code>dp[12] = True,</code> prefix <code>"ratcatdogcat"  </code> Its formed by 4 words in W <code>rat + cat +dog + cat</code> (It\'s allowed to repeat a word as <code>cat</code>).\n\nA word is concatenated if <code>dp[N] is true </code> where N is the size of W.\n<code>\n\n\t\tclass Solution {\n\t\tpublic:\n\t\t\n\t\tvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n\t\t\tvector<string> ans;\n\t\t\tunordered_set<string>dict(words.begin(),words.end());\n\t\t\t\t\n\t\t\tfor(auto w : words){\n\t\t\t\tint n = w.size();\n\t\t\t\tif(n == 0) continue;\n\t\t\t\tbool dp[n+1];\n\t\t\t\tmemset(dp,false,sizeof(dp));\n\t\t\t\tdp[0] = true;\n\t\t\t\n\t\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\t\tif(dp[i] == false) continue;\n\t\t\t\t\tstring generate="";\n\t\t\t\t\n\t\t\t\t\tfor(int j=i; j<n; j++){\n\t\t\t\t\t\tgenerate += w[j];\n\t\t\t\t\t\tif(dp[j+1])continue;\n\t\t\t\t\t\tif(i==0 && j==n-1)continue;\n\t\t\t\t\t\tif(dict.find(generate) != dict.end())\n\t\t\t\t\t\t\tdp[j+1]=true;\n\t\t\t\t\t}\n\t\t\t\t\t\n\t\t\t\t\tif(dp[n]){\n\t\t\t\t\t\tans.push_back(w);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}    \n\t\t\t}\n\t\t\t\t\t\n\t\t\treturn ans;\n\t\t}\n\t};\n</code>\n\n<b>Complexity time </b>\n* O(m * n^3) where m is the length of words and n is the average length of words.\n  \nBecause of our improvements, the complexity analysis corresponds to the worst case.\n\n<h4>Approach 2: Trie + Dynamic Programming</h4>\n<strong> Algorithm</strong>\n<p>\nFrom the previous algorithm, in this line,  <code>if(dict.find(generate) != dict.end()) </code>. We check if a substring is a word in the dictionary using <code> unordered_set</code>. We could improved it using <b>Trie</b> in constant time.\n</p>\n\n<i>\nThe improvement is not significant, due to the additional memory used to create the Trie, in addition to the weak test cases..\n</i>\n\n<code>\n\n\tclass Solution {\n\tpublic:\t\n\t\tstruct TrieNode { \n\t\t\tTrieNode *children[26];\n\t\t\tbool isTerminal; \n\t\t}; \n\t\n\t\tstruct TrieNode *getNode(void){ \n\t\t\tTrieNode *p = new TrieNode; \n\t\t\tp->isTerminal = false; \n\t\t\tfor (int i = 0; i < 26; i++) \n\t\t\t\tp->children[i] = NULL;\n\t\t\treturn p; \n\t\t} \n\t\t\n\t\tvoid add(TrieNode *p, string w){ \n\t\t\tint n = w.size(); \n\t\n\t\t\tfor (int i = 0; i < n; i++) { \n\t\t\t\tint index = w[i]-\'a\'; \n\t\t\t\tif (!p->children[index]) \n\t\t\t\t\tp->children[index] = getNode(); \n\t\t\t\tp = p->children[index]; \n\t\t\t}\n\t\n\t\t\tp->isTerminal = true; \n\t\t} \n\t\t\n\t\tvector<string> findAllConcatenatedWordsInADict(vector<string>& words){\n\t\t\tTrieNode *root = getNode();\n\t\t\t\n\t\t\tfor (int i = 0; i < words.size(); i++) \n\t\t\t\tadd(root, words[i]);\n\t\t\t\n\t\t\tvector<string> ans;\n\t\t\t\t\t\n\t\t\tfor(auto w : words){\n\t\t\t\tint n = w.size();\n\t\t\t\tif(n == 0) continue;\n\t\t\t\tbool dp[n+1];\n\t\t\t\tmemset(dp,false,sizeof(dp));\n\t\t\t\tdp[0] = true;\n\t\t\t\t\n\t\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\t\tif(dp[i] == false) continue;\n\t\t\t\t\tTrieNode *p = root;\n\t\t\t\t\t\n\t\t\t\t\tfor(int j=i;j<n;j++){\n\t\t\t\t\t\tif (!p->children[w[j]-\'a\'])break;\n\t\t\t\t\t\tp = p->children[w[j]-\'a\'];\n\t\t\t\t\t\tif(i==0 && j==n-1)continue;\n\t\t\t\t\t\tif(p->isTerminal)\n\t\t\t\t\t\t\tdp[j+1]=true;\n\t\t\t\t\t}\n\t\t\t\t\t\n\t\t\t\t\tif(dp[n]){\n\t\t\t\t\t\tans.push_back(w);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\t\n\t\t\treturn ans;\n\t\t}\n\t};\n\n</code>\n\n<b>Complexity time </b>\n\n* O(m * n^2 + K*26) where <code>m</code> is the length of words ,<code> n</code> is the average length of words and <code>K</code> is the number of nodes in the trie.\n  \n The second term represents Trie construction, 26 is the  alphabet size.  \nBecause of our improvements, the complexity analysis corresponds to the worst case.\n\nAnother implementation, without pointers, (number of nodes in the Trie is setted in <code>50000</code> because of weak cases.  \n\n<code>\n\n\tint trie[50000][26];\n\tbool terminal[50000];\n\tclass Solution {\n\tpublic:\n\t\tint node;\n\t\t\n\t\tvoid add(string s){\n\t\t\tint tam = s.size();\n\t\t\tint p = 0;    \n\t\t\tfor(int i=0;i<tam;i++){\n\t\t\t\tif(trie[p][s[i]-\'a\'] != 0){\n\t\t\t\t\tp = trie[p][s[i]-\'a\'];\n\t\t\t\t}else{\n\t\t\t\t\tp = trie[p][s[i]-\'a\'] = node++;\n\t\t\t\t}\n\t\t\t}\n\t\t\t\n\t\t\tterminal[p]= true;\n\t\t}\n\t\t\n\t\tvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n\t\t\tnode = 1;\n\t\t\tvector<string> ans;\n\t\t\tmemset(trie,0,sizeof(trie));\n\t\t\tmemset(terminal,false,sizeof(terminal));\n\t\t\t\n\t\t\tfor(int i=0;i<words.size();i++)\n\t\t\t\tadd(words[i]);\n\t\t\t\n\t\t\tfor(auto w : words){\n\t\t\t\tint n = w.size();\n\t\t\t\tif(n == 0) continue;\n\t\t\t\tbool dp[n+1];\n\t\t\t\tmemset(dp,false,sizeof(dp));\n\t\t\t\tdp[0] = true;\n\t\t\t\t\n\t\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\t\tif(dp[i] == false) continue;\n\t\t\t\t\tint index = 0;\n\t\t\t\t\t\n\t\t\t\t\tfor(int j=i;j<n;j++){\n\t\t\t\t\t\tindex = trie[index][w[j]-\'a\'];\n\t\t\t\t\t\tif(index == 0)break;\n\t\t\t\t\t\tif(i==0 && j==n-1)continue;\n\t\t\t\t\t\tif(terminal[index])\n\t\t\t\t\t\t\tdp[j+1]=true;\n\t\t\t\t\t}\n\t\t\t\t\t\n\t\t\t\t\tif(dp[n]){\n\t\t\t\t\t\tans.push_back(w);\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}    \n\t\t\t}\n\t\t\t\n\t\t\treturn ans;\n\t\t}\n\t};\n</code>\n\n
['Dynamic Programming', 'Trie']