// 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); }