From 64b99fa5197737fab06e6e8465a203be985b07a8 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 13 Sep 2025 21:38:41 -0600 Subject: 966. vowel spellchecker --- vowel_spellchecker.c | 168 ++++++++++++++++++++++++++++++++++++++++++++++++++ vowel_spellchecker.py | 58 +++++++++++++++++ 2 files changed, 226 insertions(+) create mode 100644 vowel_spellchecker.c create mode 100644 vowel_spellchecker.py 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"])) -- cgit v1.2.3