C++ || Simple DP (With Full Explanation) || Beats 99% 🏁🔥
Intuition\nThe intuition behind this solution is to use dynamic programming to check if a word can be constructed by the concatenation of other words in the set
# Intuition\nThe intuition behind this solution is to use dynamic programming to check if a word can be constructed by the concatenation of other words in the set.\n\n# Approach\nFirst, the input list of words is converted into an unordered_set, which is an efficient data structure for checking if a word is in the set in constant time. Then, an empty vector res is created to store the concatenated words that are found.\n\nThe code then iterates over the input list of words. For each word, it creates a vector dp of size n+1 where n is the length of the word. This vector is used to store whether it is possible to construct the word until a certain index by concatenating other words in the set. The vector is initially set to 0 for all indices, except for the first element, which is set to 1.\n\nThe code then iterates over the word again, and for each index i, it checks if the dp value at index i is 1, which means it is possible to construct the word until this index by concatenating other words. If so, it checks if there is a word in the set that starts from this index and has a length j - i, where j is the next index. If such a word is found, it updates the dp value at index j to 1.\n\nFinally, after iterating over the word, the code checks if the dp value at the last index is 1, which means that the word can be constructed by the concatenation of other words in the set. If so, it adds the word to the result vector.\n\nAfter iterating over all the words, the code returns the result vector, which contains all the concatenated words in the input list of words.\n\n\uD83D\uDCCD Here is an example of how the code would work for the word "catdog" and the set of words {"cat","dog"}:\n1. First, the input list of words is converted into an unordered_set, which is an efficient data structure for checking if a word is in the set in constant time.\n2. Then, an empty vector res is created to store the concatenated words that are found.\n3. The code then iterates over the input list of words. For each word "catdog", it creates a vector dp of size n+1 where n is the length of the word. This vector is used to store whether it is possible to construct the word until a certain index by concatenating other words in the set. The vector is initially set to 0 for all indices, except for the first element, which is set to 1.\n    ```\n    dp = [1, 0, 0, 0, 0, 0, 0]\n\n    ```\n4. The code then iterates over the word again, and for each index i, it checks if the dp value at index i is 1, which means it is possible to construct the word until this index by concatenating other words. If so, it checks if there is a word in the set that starts from this index and has a length j - i, where j is the next index. If such a word is found, it updates the dp value at index j to 1.\n    ```\n    i = 0, j = 3, check if "cat" is in set: Yes, update dp[3] = 1\n    i = 3, j = 6, check if "dog" is in set: Yes, update dp[6] = 1\n    ```\n5. Finally, after iterating over the word, the code checks if the dp value at the last index is 1, which means that the word can be constructed by the concatenation of other words in the set. If so, it adds the word to the result vector.\n    ```\n    dp = [1, 0, 0, 1, 0, 0, 1]\n\n    ```\n\nAs the dp array\'s last index is 1, which means the word "catdog" can be constructed by the concatenation of other words in the set, so it\'s added to the result vector.\n\nIn this way, this approach is checking if a word is a concatenated word by breaking it down into substrings and checking if each substring is a word in the set, making use of a dp array to store intermediate results. This method is much more efficient than checking all possible concatenations of words.\n\n# Complexity\n- **Time complexity:**\nThe time complexity of this solution is **O(n * L^2)**, where n is the number of words in the input list and L is the maximum length of the words.\nThe main source of the time complexity is the nested loops that iterate over the words and the characters of the words. The outer loop iterates over the words and has a time complexity of O(n). The inner loop iterates over the characters of the words and has a time complexity of O(L). The inner loop also performs additional operations, such as checking if a word is in the set and updating the dp array, which also contribute to the overall time complexity.\n\n- **Space complexity:**\nThe space complexity is **O(n * L)**, where n is the number of words in the input list and L is the maximum length of the words. The main source of the space complexity is the dp array, which is created for each word and has a size of L. Additionally, creating a unordered_set of all the words also takes O(n) space.\n\n# Code\n```\nclass Solution {\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        unordered_set<string> words_set;\n        for (string word : words) words_set.insert(word);\n        vector<string> res;\n    \n        for (string word : words) {\n            int n = word.size();\n            vector<int> 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 (j - i < n && words_set.count(word.substr(i, j - i))) {\n                        dp[j] = 1;\n                    }\n                }\n                if (dp[n]) {\n                    res.push_back(word);\n                    break;\n                }\n            }\n        }\n        return res;\n    }\n};\n```\n\n\n![2wlbi6.webp](https://assets.leetcode.com/users/images/b96b0303-1829-44d2-b5c9-f052e1a797da_1674782842.712479.webp)\n
['String', 'Dynamic Programming', 'Depth-First Search', 'C++']