Partition Dp Solution || C++ || Easy Understanding
\n\nT.C : O(n*s[i].length)\nS.C : O(n * s[i].length)\n\n\n\nclass Solution {\npublic:\n    unordered_set<string> mp;\n    // dp[i] = number of ways to partition
\n\n**T.C : O(n*s[i].length)\nS.C : O(n * s[i].length)**\n\n\n```\nclass Solution {\npublic:\n    unordered_set<string> mp;\n    // dp[i] = number of ways to partition strings such that each substring is in the words;\n    int rec(string &s,int n,int i,vector<int> &dp){\n        if(i>=n) return true;\n        if(dp[i]!=-1) return dp[i];\n        dp[i] = 0;\n        for(int j=i;j<n;j++){\n            string tmp = s.substr(i,j-i+1);\n            if(mp.count(tmp)){ // if substring is in words.\n                dp[i] += rec(s,n,j+1,dp);\n            }\n        }\n        return dp[i];\n    }\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words){\n        mp.clear();\n        vector<string> ans;\n        for(auto &ele:words) mp.insert(ele);\n        for(auto &ele:words){\n            vector<int> dp(ele.size()+1,-1);\n            int ways = rec(ele,ele.size(),0,dp);\n            if(ways>1){ // we can always partition whole string so that way is not considered.\n                ans.push_back(ele);\n            }\n        }\n        return ans;\n    }\n};\n```\n\nPlease upvote if you like the solution !!
['Dynamic Programming', 'C']