{"id":"805bb13a-fca6-484b-8b92-d782ea235f4e","name":"Concatenated Words","description":"Given an array of strings words, return all the concatenated words in the given list of words.\r\nConcatenated word is a word that can be created by concatination of at least two other shorter words from the list.\r\n\r\nYou can return concatination words in any order","inputFormat":"n count of words in list\r\nword1\r\nword2\r\n... n words","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= words.length &lt;= 10^4\r\n2. 1 &lt;= words[i].length &lt;= 1000\r\n3. words[i] consists of only lowercase English letters.\r\n4. all word's in the list are unique.\r\n5. 0 &lt;= sum(words[i].length) &lt;= 10^5","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n\n\n\nvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n\n // write your code here\n}\n\n\n\n\nint main() {\n int n ;\n cin>>n;\n\n vector<string> words(n);\n for (int i = 0; i < n ; i++) {\n cin>>words[i];\n }\n \n \n \n vector<string> result = findAllConcatenatedWordsInADict(words);\nsort(result.begin(), result.end());\n\n for (string s : result) {\n cout << s << endl;\n }\n\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static List<String> findAllConcatenatedWordsInADict(String[] words) {\r\n\r\n return null;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n\r\n String[]words = new String[n];\r\n\r\n for(int i=0;i<n;i++){\r\n words[i] = read.readLine();\r\n }\r\n\r\n List<String> result = findAllConcatenatedWordsInADict(words);\r\n Collections.sort(result);\r\n PrintWriter out = new PrintWriter(System.out);\r\n for(String s: result){\r\n out.println(s);\r\n }\r\n out.close();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8\r\ncat\r\ncats\r\ncatsdogcats\r\ndog\r\ndogcatsdog\r\nhippopotamuses\r\nrat\r\nratcatdogcat","sampleOutput":"catsdogcats\r\ndogcatsdog\r\nratcatdogcat\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"4b4725b5-4896-4b68-aae2-03ea1e2ecbb2","name":"Trie For Intermediate","slug":"trie-for-intermediate-9996","type":0},{"id":"a1a4e8d0-7fca-4c3e-b696-12289db0b315","name":"Concatenated Words MCQ","slug":"concatenated-words-mcq","type":0},{"id":"faa7850b-baf2-4170-a519-d368f2399c57","name":"Concatenated Words","slug":"concatenated-words","type":1}],"next":null,"prev":null}}

Concatenated Words

Given an array of strings words, return all the concatenated words in the given list of words. Concatenated word is a word that can be created by concatination of at least two other shorter words from the list. You can return concatination words in any order

{"id":"805bb13a-fca6-484b-8b92-d782ea235f4e","name":"Concatenated Words","description":"Given an array of strings words, return all the concatenated words in the given list of words.\r\nConcatenated word is a word that can be created by concatination of at least two other shorter words from the list.\r\n\r\nYou can return concatination words in any order","inputFormat":"n count of words in list\r\nword1\r\nword2\r\n... n words","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= words.length &lt;= 10^4\r\n2. 1 &lt;= words[i].length &lt;= 1000\r\n3. words[i] consists of only lowercase English letters.\r\n4. all word's in the list are unique.\r\n5. 0 &lt;= sum(words[i].length) &lt;= 10^5","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n\n\n\nvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n\n // write your code here\n}\n\n\n\n\nint main() {\n int n ;\n cin>>n;\n\n vector<string> words(n);\n for (int i = 0; i < n ; i++) {\n cin>>words[i];\n }\n \n \n \n vector<string> result = findAllConcatenatedWordsInADict(words);\nsort(result.begin(), result.end());\n\n for (string s : result) {\n cout << s << endl;\n }\n\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static List<String> findAllConcatenatedWordsInADict(String[] words) {\r\n\r\n return null;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n = Integer.parseInt(read.readLine());\r\n\r\n String[]words = new String[n];\r\n\r\n for(int i=0;i<n;i++){\r\n words[i] = read.readLine();\r\n }\r\n\r\n List<String> result = findAllConcatenatedWordsInADict(words);\r\n Collections.sort(result);\r\n PrintWriter out = new PrintWriter(System.out);\r\n for(String s: result){\r\n out.println(s);\r\n }\r\n out.close();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"8\r\ncat\r\ncats\r\ncatsdogcats\r\ndog\r\ndogcatsdog\r\nhippopotamuses\r\nrat\r\nratcatdogcat","sampleOutput":"catsdogcats\r\ndogcatsdog\r\nratcatdogcat\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"4b4725b5-4896-4b68-aae2-03ea1e2ecbb2","name":"Trie For Intermediate","slug":"trie-for-intermediate-9996","type":0},{"id":"a1a4e8d0-7fca-4c3e-b696-12289db0b315","name":"Concatenated Words MCQ","slug":"concatenated-words-mcq","type":0},{"id":"faa7850b-baf2-4170-a519-d368f2399c57","name":"Concatenated Words","slug":"concatenated-words","type":1}],"next":null,"prev":null}}
plane

Editor


Loading...

Concatenated Words

hard

Given an array of strings words, return all the concatenated words in the given list of words. Concatenated word is a word that can be created by concatination of at least two other shorter words from the list. You can return concatination words in any order

Constraints

1. 1 <= words.length <= 10^4 2. 1 <= words[i].length <= 1000 3. words[i] consists of only lowercase English letters. 4. all word's in the list are unique. 5. 0 <= sum(words[i].length) <= 10^5

Format

Input

n count of words in list word1 word2 ... n words

Output

Output is managed for you

Example

Sample Input

8 cat cats catsdogcats dog dogcatsdog hippopotamuses rat ratcatdogcat

Sample Output

catsdogcats dogcatsdog ratcatdogcat

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode