aboutsummaryrefslogtreecommitdiff
path: root/replace_words.c
diff options
context:
space:
mode:
Diffstat (limited to 'replace_words.c')
-rw-r--r--replace_words.c98
1 files changed, 98 insertions, 0 deletions
diff --git a/replace_words.c b/replace_words.c
new file mode 100644
index 0000000..ed509d0
--- /dev/null
+++ b/replace_words.c
@@ -0,0 +1,98 @@
+// 648. Replace Words
+#include "leetcode.h"
+
+/*
+ * in english we have a concept called root, which can be followed by some other
+ * word to form another longer word lets call this word derivative. for example
+ * when the root "help" is followed by the word "ful" we can form a derivative
+ * "helpful". given a dictionary consisting of many roots and a 'sentence'
+ * consisting of words separated by spaces, replace all the derivatives in the
+ * sentence with the root forming it. if a derivative can be replaced by more
+ * than one root, replace it with the root that has the shortest length. return
+ * the 'sentence' after the replacement
+ */
+
+typedef struct Trie {
+ struct Trie *children[26];
+ bool is_leaf;
+} Trie;
+
+Trie *create() {
+ Trie *node = (Trie *)malloc(sizeof(Trie));
+ for (int i = 0; i < 26; i++)
+ node->children[i] = NULL;
+ node->is_leaf = false;
+ return node;
+}
+
+void insert(Trie *obj, char *word) {
+ Trie *tmp = obj;
+ for (int i = 0; word[i] != '\0'; i++) {
+ int idx = word[i] - 'a';
+ if (!tmp->children[idx])
+ tmp->children[idx] = create();
+ tmp = tmp->children[idx];
+ }
+ tmp->is_leaf = true;
+}
+
+int trieSearch(Trie *obj, char *word) {
+ Trie *tmp = obj;
+ int curr = 0;
+ for (int i = 0; word[i] != '\0'; i++) {
+ if (word[i] == ' ')
+ return 0;
+ int idx = word[i] - 'a';
+ if (!tmp->children[idx])
+ return 0;
+ curr++;
+ if (tmp->children[idx]->is_leaf)
+ return curr;
+ tmp = tmp->children[idx];
+ }
+ return 0;
+}
+
+int substring(char *str) {
+ int l = strlen(str);
+ for (int i = 0; i < l; i++)
+ if (str[i] == ' ') {
+ str[i] = '\0';
+ return i;
+ }
+ return l;
+}
+
+char *replaceWords(char **dictionary, int dictionarySize, char *sentence) {
+ Trie *root = create();
+ for (int i = 0; i < dictionarySize; i++)
+ insert(root, dictionary[i]);
+ int len = strlen(sentence), a_idx = 0, idx = 0;
+ char *ans = (char *)malloc((len + 1) * sizeof(char));
+ while (idx < len) {
+ int d = substring(&sentence[idx]);
+ int l = trieSearch(root, &sentence[idx]);
+ if (l) {
+ strncpy(&ans[a_idx], &sentence[idx], l);
+ ans[a_idx + l] = ' ';
+ a_idx += l + 1;
+ } else {
+ strncpy(&ans[a_idx], &sentence[idx], d);
+ ans[a_idx + d] = ' ';
+ a_idx += d + 1;
+ }
+ idx += d + 1;
+ }
+ ans[a_idx - 1] = '\0';
+ return ans;
+}
+
+int main() {
+ char *d1[] = {"cat", "bat", "rat"}, *d2[] = {"a", "b", "c"};
+ char *s1 = "the cattle was rattled by the battery",
+ *s2 = "aadsfasf absbs bbab cadsfafs";
+ printf("%s\n", replaceWords((char **)d1, ARRAY_SIZE(d1),
+ s1)); // expect: the cat was rat by the bat
+ printf("%s\n",
+ replaceWords((char **)d2, ARRAY_SIZE(d2), s2)); // expect: a a b c
+}