Dictionary Implementation with suggestions

Implement a spell checker using a hash table to store a dictionary of words for fast lookup. Implement functions to check if a word is valid and to suggest corrections for misspelled words.

A spell checker needs:

1. Fast lookup of words (dictionary storage).

2. Check validity → is the word in the dictionary?

3. Suggest corrections → usually done by generating candidate words close to the misspelled one (edit distance 1: insertion, deletion, substitution, transposition).

---

✅ Design (Hash Table for Dictionary)

• Hash table (array of linked lists for collisions).

• Each bucket stores words that hash to that index.

• Operations:

  • Insert(word) → store dictionary word.

  • Search(word) → check if valid.

• For suggestions, generate possible edits and check in the hash table.

C Program Implementation

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#define TABLE_SIZE 1000

#define WORD_LEN 50

// Node for linked list (chaining)

typedef struct Node {

    char word[WORD_LEN];

    struct Node* next;

} Node;

Node* hashTable[TABLE_SIZE];

// Hash function (djb2)

unsigned int hash(const char* str) {

    unsigned long hash = 5381;

    int c;

    while ((c = *str++))

        hash = hash*33 + c;

    return hash % TABLE_SIZE;

}

// Insert word into hash table

void insert(const char* word) {

    unsigned int index = hash(word);

    Node* newNode = (Node*)malloc(sizeof(Node));

    strcpy(newNode->word, word);

    newNode->next = hashTable[index];

    hashTable[index] = newNode;

}

// Search word in hash table

int search(const char* word) {

    unsigned int index = hash(word);

    Node* curr = hashTable[index];

    while (curr) {

        if (strcmp(curr->word, word) == 0)

            return 1;

        curr = curr->next;

    }

    return 0;

}

// Suggest corrections (edit distance 1)

void suggest(const char* word) {

    char temp[WORD_LEN];

    int len = strlen(word);

    printf("Did you mean:\n");

    // Substitution

    for (int i = 0; i < len; i++) {

        for (char c = 'a'; c <= 'z'; c++) {

            strcpy(temp, word);

            temp[i] = c;

            if (search(temp) && strcmp(temp, word) != 0)

                printf("  %s\n", temp);

        }

    }

    // Insertion

    for (int i = 0; i <= len; i++) {

        for (char c = 'a'; c <= 'z'; c++) {

            strcpy(temp, word);

            memmove(temp + i + 1, temp + i, len - i + 1);

            temp[i] = c;

            if (search(temp))

                printf("  %s\n", temp);

        }

    }

    // Deletion

    for (int i = 0; i < len; i++) {

        strcpy(temp, word);

        memmove(temp + i, temp + i + 1, len - i);

        if (search(temp))

            printf("  %s\n", temp);

    }

}

int main() {

    // Build dictionary

    char* dictionary[] = {"apple", "apply", "bat", "ball", "cat", "dog", "cart","dog","elephant"};

    int dictSize = sizeof(dictionary) / sizeof(dictionary[0]);

    for (int i = 0; i < dictSize; i++) {

        insert(dictionary[i]);

    }

    char word[WORD_LEN];

    printf("Enter a word to check: ");

    scanf("%s", word);

    if (search(word)) {

        printf("'%s' is spelled correctly.\n", word);

    } else {

        printf("'%s' is NOT in dictionary.\n", word);

        suggest(word);

    }

    return 0;

}

Enter a word to check: elepant

'elepant' is NOT in dictionary.

Did you mean:

  elephant