✅C++|Very Simple DP |Beats 90%🔥✔
Intuition\n Describe your first thoughts on how to solve this problem. \nIdea is to check if a word  can be constructed by the concatenation of other words in t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIdea is to check if a word  can be constructed by the concatenation of other words in the set. Actually first fill all the word in aset that is a perfect data structure to check if a word s present or not . \n# Approach\n<!-- Describe your approach to solving the problem. -->\nSo here we have to check for substring of a word is presnt or not if starting substring is not present then no need to get further if presnt then we add up and atlast check if dp[n] is true or not ,if yes then we push the word in ans vector. \nActually DP array will track the  substring  upto some index is present or not and at n the index if it is true in dp array then whole word is found and then we push_back that word.\n# Complexity\n- Time complexity:$$O(N*W^3)$$\n  - where N=words.length() and W=words[i].length()\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(N*W)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        unordered_set<string>word_set(words.begin(),words.end());\n        vector<string>ans;\n        for(auto w:words){\n            int n=w.size();\n            vector<bool>dp(n+1,false);\n            dp[0]=1;\n            for(int i=0;i<n;i++){\n                if(!dp[i])continue;\n                for(int j=i+1;j<=n;j++){\n                    if(j-i<n and word_set.count(w.substr(i,j-i)))\n                    dp[j]=1;\n                }\n            }\n            if(dp[n]==1)ans.push_back(w);\n        }\n       return ans;\n    }\n};\n```
['Hash Table', 'String', 'Dynamic Programming', 'Depth-First Search', 'C++']