Create 472.Concatenated-Words.cpp

wisdompeak · web-flow · commit a3d173c5c014 · 2021-04-27T00:02:48.000-07:00
diff --git a/Trie/472.Concatenated-Words/472.Concatenated-Words.cpp b/Trie/472.Concatenated-Words/472.Concatenated-Words.cpp
@@ -0,0 +1,72 @@
+class Solution {
+    class TrieNode
+    {
+        public:
+        TrieNode* next[26];
+        bool isEnd;
+        TrieNode()
+        {
+            for (int i=0; i<26; i++)
+                next[i] = NULL;
+            isEnd = false;
+        }
+    };
+    TrieNode* root;
+public:
+    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) 
+    {       
+        sort(words.begin(), words.end(), [](string&a, string&b){return a.size()<b.size();});
+        root = new TrieNode();
+
+        vector<string>rets;
+        for (auto word: words)
+        {
+            if (word!="" && check(word, root))
+                rets.push_back(word);
+
+            TrieNode* node = root;
+            for (auto ch:word)
+            {
+                if (node->next[ch-'a']==NULL)
+                    node->next[ch-'a'] = new TrieNode();
+                node = node->next[ch-'a'];
+            }
+            node->isEnd = true;
+        }
+        return rets;
+    }
+
+    bool check(string& word, TrieNode* root)
+    {
+        int n = word.size();
+        vector<int>visited(n,0);
+        return dfs(word, root, 0, visited);
+    }
+
+    bool dfs(string& word, TrieNode* root, int cur, vector<int>&visited)
+    {
+        if (cur==word.size()) return true;
+
+        if (visited[cur]==1)
+            return false;
+
+        TrieNode* node = root;
+
+        for (int i=cur; i<word.size(); i++)
+        {
+            if (node->next[word[i]-'a']!=NULL)
+            {
+                node = node->next[word[i]-'a'];
+                if (node->isEnd && dfs(word, root, i+1, visited))
+                    return true;                
+            } 
+            else
+            {
+                break;
+            }
+        }
+
+        visited[cur] = 1;
+        return false;
+    }
+};
