aboutsummaryrefslogtreecommitdiff
path: root/concatenated_words.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /concatenated_words.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'concatenated_words.cpp')
-rw-r--r--concatenated_words.cpp75
1 files changed, 75 insertions, 0 deletions
diff --git a/concatenated_words.cpp b/concatenated_words.cpp
new file mode 100644
index 0000000..9263d87
--- /dev/null
+++ b/concatenated_words.cpp
@@ -0,0 +1,75 @@
+// 472. Concatenated Words
+#include "leetcode.h"
+
+/*
+ * 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 as string that is comprised entirely of at least two shorter
+ * words in the given array.
+ */
+
+class Solution {
+private:
+ struct Trie {
+ struct Trie *arr[26];
+ bool end = false;
+ Trie() {
+ memset(arr, 0, sizeof(arr));
+ end = false;
+ }
+ };
+ Trie *root;
+ void insert(string s) {
+ Trie *node = root;
+ for (int i = s.length() - 1; i >= 0; i--) {
+ char c = s[i];
+ if (!node->arr[c - 'a'])
+ node->arr[c - 'a'] = new Trie();
+ node = node->arr[c - 'a'];
+ }
+ node->end = true;
+ }
+
+public:
+ vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
+ sort(words.begin(), words.end(),
+ [](string &w1, string &w2) { return (w1.length() <= w2.length()); });
+ vector<string> ans;
+ root = new Trie();
+ for (string w : words) {
+ if (w.length() == 0)
+ continue;
+ vector<bool> dp(w.length() + 1, false);
+ dp[0] = true;
+ for (int i = 0; i < w.length(); i++) {
+ Trie *node = root;
+ for (int j = i; j >= 0; j--) {
+ if (node->arr[w[j] - 'a'] == NULL)
+ break;
+ node = node->arr[w[j] - 'a'];
+ if (dp[j] && node->end) {
+ dp[i + 1] = true;
+ break;
+ }
+ }
+ }
+ if (dp[w.length()])
+ ans.push_back(w);
+ insert(w);
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<string> words1 = {"cat", "cats", "catsdogcats",
+ "dog", "dogcatsdog", "hippopotamuses",
+ "rat", "ratcatdogcat"};
+ vector<string> words2 = {"cat", "dog", "catdog"};
+ for (auto i : obj.findAllConcatenatedWordsInADict(words1))
+ cout << i << ' ';
+ cout << endl;
+ for (auto i : obj.findAllConcatenatedWordsInADict(words2))
+ cout << i << ' ';
+}