🔥C++|Template for Word Break I,II,Concatenated-words|All U Need✅
Intuition\n Describe your first thoughts on how to solve this problem. \nIntuition for all the problems:\nAll the three given problems  can be divided into sub-
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIntuition for all the problems:\nAll the three given problems  can be divided into sub-problems .And  If these subproblems individually satisfy the required conditions, then  complete problem will also satisfy the same. And hence we can say whether it is true to find the word in the dictionary or not.\n\n# Approach\n- **Naive Approach**: Use recursion and backtracking. For finding the solution, we check every prefix of the string in the word_dict of words, if it is found , then the recursive function is called for the remaining portion of that string. But this will be$$ 2^n$$ so will give tle . SO we can optimize using memoization or dp.\n- **DP**: So as we can see that in recurion we call for evrery prefix substring and check if its presnt and like this the we check the whole is present or not .So similarly we can store the same ,like upto certain index whether the substring upto that index is present or not . In this way our dp array will be filled with 0\'s and 1\'s representing whether the substring upto that index is present or not . And at last if last index is true i.e dp[n] is true this means whole string is presnt .\n- So applying this logic we can do all the three problems with a little modification based on requirements.\n<!-- Describe your approach to solving the problem. -->\n# **For Word Break I**\n\n# Code\n\n```\n bool wordBreak(string s, vector<string>& wordDict) {\n        unordered_set<string>word_set(wordDict.begin(),wordDict.end());\n        int n=s.size();\n        vector<bool>dp(n+1,0);\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( word_set.count(s.substr(i,j-i)))\n                dp[j]=1;\n            }\n        }\n        return dp[n];\n    }\n```\n# Complexity\n- Time complexity:$$O(N^3)$$\n    - $$N^2$$ for two loops and N for `substr`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# **For Word Break II**\n```\nvector<string> wordBreak(string s, vector<string>& wordDict) {\n        int n=s.size();\n        unordered_set<string>word_Set(wordDict.begin(),wordDict.end());\n         vector<vector<string>>dp(n+1,vector<string>());\n         dp[0].push_back("");\n    \n          for(int i = 0; i < n; ++i){\n            for(int j = i+1; j <= n; ++j){\n                string temp = s.substr(i, j-i);\n                if(word_Set.count(temp)){\n                    for(auto x : dp[i]){\n                        dp[j].emplace_back(x + (x == "" ? "" : " ") + temp);  \n                    }\n                }\n            }\n        }\n         return dp[n];\n    }\n```\n# Complexity\n- Time complexity:$$O(N^3)$$\n    - $$N^2$$ for two loops and N for `substr`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(N^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# **For concatenated Words**\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```\n# Complexity\n- Time complexity:$$O(N*W^3)$$\n    - where `N=word.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
['Hash Table', 'Dynamic Programming', 'Backtracking', 'Depth-First Search', 'C++']