aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-13 21:38:41 -0600
committerJack Sangdahl <[email protected]>2025-09-13 21:38:41 -0600
commit64b99fa5197737fab06e6e8465a203be985b07a8 (patch)
treef48437ea05d7e77b1f1b59b8bcaac015438a09aa
parent77d6e1dd41c644ed28fb61a3f19614965b43908c (diff)
downloadleetcode-64b99fa5197737fab06e6e8465a203be985b07a8.tar.gz
leetcode-64b99fa5197737fab06e6e8465a203be985b07a8.zip
966. vowel spellchecker
-rw-r--r--vowel_spellchecker.c168
-rw-r--r--vowel_spellchecker.py58
2 files changed, 226 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);
+}
diff --git a/vowel_spellchecker.py b/vowel_spellchecker.py
new file mode 100644
index 0000000..ca1ad43
--- /dev/null
+++ b/vowel_spellchecker.py
@@ -0,0 +1,58 @@
+# 966. Vowel Spellchecker
+
+"""
+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]'
+"""
+
+
+class Solution(object):
+ def spellchecker(self, wordlist, queries):
+ """
+ :type wordlist: List[str]
+ :type queries: List[str]
+ :rtype: List[str]
+ """
+
+ def mask(s):
+ return "".join("*" if c in "aeiou" else c for c in s.lower())
+
+ hash1 = set(wordlist)
+ hash2 = {s.lower(): s for s in wordlist[::-1]}
+ hash3 = {mask(s): s for s in wordlist[::-1]}
+
+ def solve(query):
+ if query in hash1:
+ return query
+ if query.lower() in hash2:
+ return hash2[query.lower()]
+ if mask(query) in hash3:
+ return hash3[mask(query)]
+ return ""
+
+ return [solve(q) for q in queries]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.spellchecker(
+ wordlist=["KiTe", "kite", "hare", "Hare"],
+ queries=[
+ "kite",
+ "Kite",
+ "KiTe",
+ "Hare",
+ "HARE",
+ "Hear",
+ "hear",
+ "keti",
+ "keet",
+ "keto",
+ ],
+ )
+ )
+ print(obj.spellchecker(wordlist=["yellow"], queries=["YellOw"]))