aboutsummaryrefslogtreecommitdiff
path: root/vowel_spellchecker.c
diff options
context:
space:
mode:
Diffstat (limited to 'vowel_spellchecker.c')
-rw-r--r--vowel_spellchecker.c168
1 files changed, 168 insertions, 0 deletions
diff --git a/vowel_spellchecker.c b/vowel_spellchecker.c
new file mode 100644
index 0000000..3a7af1c
--- /dev/null
+++ b/vowel_spellchecker.c
@@ -0,0 +1,168 @@
+// 966. Vowel Spellchecker
+#include "leetcode.h"
+
+/*
+ * given a 'wordlist', we want to implement a spellchecker that converts a query
+ * word into a correct word. for a given 'query', the spell checker handles two
+ * categories of spelling mistakes: capitalisation and vowel errors. given some
+ * 'queries', return a list of words 'answer' where 'answer[i]' is the correct
+ * word for 'query = queries[i]'
+ */
+
+unsigned int rs_hash1(char *s) {
+ unsigned int a = 63689, b = 378551, hash = 0;
+ while (*s) {
+ hash = hash * a + (*s++);
+ a *= b;
+ }
+ return hash & 0x7FFFFFFF;
+}
+
+unsigned int rs_hash2(char *s) {
+ unsigned int a = 63689, b = 378551, hash = 0;
+ while (*s) {
+ char curr = *s;
+ if (curr >= 'A' && curr <= 'Z')
+ curr = curr - 'A' + 'a';
+ hash = hash * a + curr;
+ (*s)++;
+ a *= b;
+ }
+ return hash & 0x7FFFFFFF;
+}
+
+unsigned int rs_hash3(char *s) {
+ unsigned int a = 63689, b = 378551, hash = 0;
+ while (*s) {
+ char curr = *s;
+ if (curr == 'a' || curr == 'e' || curr == 'i' || curr == 'o' || curr == 'u')
+ curr = 'A';
+ else if (curr == 'A' || curr == 'E' || curr == 'I' || curr == 'O' ||
+ curr == 'U')
+ curr = 'A';
+ else if (curr >= 'A' && curr <= 'Z')
+ curr = curr - 'A' + 'a';
+ hash = hash * a + curr;
+ (*s)++;
+ a *= b;
+ }
+ return hash & 0x7FFFFFFF;
+}
+
+char **spellchecker(char **wordlist, int wordlistSize, char **queries,
+ int queriesSize, int *returnSize) {
+ int n = wordlistSize * 10;
+ unsigned int **hash1 = (unsigned int **)calloc(n, sizeof(unsigned int *));
+ unsigned int **hash2 = (unsigned int **)calloc(n, sizeof(unsigned int *));
+ unsigned int **hash3 = (unsigned int **)calloc(n, sizeof(unsigned int *));
+ for (int i = 0; i < wordlistSize; i++) {
+ unsigned int val = rs_hash1(wordlist[i]), d = val;
+ while (1) {
+ if (!hash1[d % n]) {
+ hash1[d % n] = (unsigned int *)malloc(2 * sizeof(unsigned int));
+ hash1[d % n][0] = val;
+ hash1[d % n][1] = i;
+ break;
+ } else
+ d++;
+ }
+ val = rs_hash2(wordlist[i]);
+ d = val;
+ while (1) {
+ if (!hash2[d % n]) {
+ hash2[d % n] = (unsigned int *)malloc(2 * sizeof(unsigned int));
+ hash2[d % n][0] = val;
+ hash2[d % n][1] = i;
+ break;
+ } else
+ d++;
+ }
+ val = rs_hash3(wordlist[i]);
+ d = val;
+ while (1) {
+ if (!hash3[d % n]) {
+ hash3[d % n] = (unsigned int *)malloc(2 * sizeof(unsigned int));
+ hash3[d % n][0] = val;
+ hash3[d % n][1] = i;
+ break;
+ } else
+ d++;
+ }
+ }
+ char **ans = (char **)malloc(queriesSize * sizeof(char *));
+ unsigned int val, d;
+ for (int i = 0; i < queriesSize; i++) {
+ ans[i] = (char *)malloc(8 * sizeof(char));
+ val = rs_hash1(queries[i]);
+ d = val;
+ while (1) {
+ if (!hash1[d % n])
+ break;
+ else if (hash1[d % n][0] == val) {
+ int pos = hash1[d % n][1];
+ strcpy(ans[i], wordlist[pos]);
+ goto next;
+ } else
+ d++;
+ }
+ val = rs_hash2(queries[i]);
+ d = val;
+ while (1) {
+ if (!hash2[d % n])
+ break;
+ else if (hash2[d % n][0] == val) {
+ int pos = hash2[d % n][1];
+ strcpy(ans[i], wordlist[pos]);
+ goto next;
+ } else
+ d++;
+ }
+ val = rs_hash3(queries[i]);
+ d = val;
+ while (1) {
+ if (!hash3[d % n])
+ break;
+ else if (hash3[d % n][0] == val) {
+ int pos = hash3[d % n][1];
+ strcpy(ans[i], wordlist[pos]);
+ goto next;
+ } else
+ d++;
+ }
+ ans[i] = "";
+ next:
+ continue;
+ }
+ free(hash1);
+ free(hash2);
+ free(hash3);
+ *returnSize = queriesSize;
+ return ans;
+}
+
+int main() {
+ char *w1[] = {"KiTe", "kite", "hare", "Hare"},
+ *q1[] = {"kite", "Kite", "KiTe", "Hare", "HARE",
+ "Hear", "hear", "keti", "keet", "keto"};
+ char *w2[] = {"yellow"}, *q2[] = {"YellOw"};
+ int rs1, rs2;
+ char **sc1 = spellchecker((char **)w1, ARRAY_SIZE(w1), (char **)q1,
+ ARRAY_SIZE(q1), &rs1);
+ char **sc2 = spellchecker((char **)w2, ARRAY_SIZE(w2), (char **)q2,
+ ARRAY_SIZE(q2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf(
+ "%s ",
+ sc1[i]); // expect:
+ // ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%s ", sc2[i]); // expect: ["yellow"]
+ printf("\n");
+ for (int i = 0; i < rs1; i++)
+ free(sc1[i]);
+ free(sc1);
+ for (int i = 0; i < rs2; i++)
+ free(sc2[i]);
+ free(sc2);
+}