Concatenated Words – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Example 2:
Input: words = ["cat","dog","catdog"] Output: ["catdog"]
Constraints:
1 <= words.length <= 1041 <= words[i].length <= 30words[i]consists of only lowercase English letters.- All the strings of
wordsare unique. 1 <= sum(words[i].length) <= 105
C++ Concatenated Words LeetCode Solution
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> s(words.begin(), words.end());
vector<string> res;
for (auto w : words) {
int n = w.size();
vector<int> dp(n+1);
dp[0] = 1;
for (int i = 0; i < n; i++) {
if (dp[i] == 0) continue;
for (int j = i+1; j <= n; j++) {
if (j - i < n && s.count(w.substr(i, j-i))) dp[j] = 1;
}
if (dp[n]) { res.push_back(w); break; }
}
}
return res;
}
Java Concatenated Words LeetCode Solution
public class Solution {
public static List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> result = new ArrayList<>();
Set<String> preWords = new HashSet<>();
Arrays.sort(words, new Comparator<String>() {
public int compare (String s1, String s2) {
return s1.length() - s2.length();
}
});
for (int i = 0; i < words.length; i++) {
if (canForm(words[i], preWords)) {
result.add(words[i]);
}
preWords.add(words[i]);
}
return result;
}
private static boolean canForm(String word, Set<String> dict) {
if (dict.isEmpty()) return false;
boolean[] dp = new boolean[word.length() + 1];
dp[0] = true;
for (int i = 1; i <= word.length(); i++) {
for (int j = 0; j < i; j++) {
if (!dp[j]) continue;
if (dict.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[word.length()];
}
}
Python 3 Concatenated Words LeetCode Solution
class Solution(object):
def findAllConcatenatedWordsInADict(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
d = set(words)
def dfs(word):
for i in range(1, len(word)):
prefix = word[:i]
suffix = word[i:]
if prefix in d and suffix in d:
return True
if prefix in d and dfs(suffix):
return True
if suffix in d and dfs(prefix):
return True
return False
res = []
for word in words:
if dfs(word):
res.append(word)
return res
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
