The Word Ladder Problem involves transforming a starting word into an ending word by changing one letter at a time. Each intermediate word must exist in a given dictionary. This program utilizes the Breadth-First Search (BFS) algorithm to find the shortest transformation sequence.

Program Structure

• Include Libraries:Standard libraries for input/output operations and string manipulation.
• Data Structures:Use a queue to manage the BFS and a set to store valid words.
• Functions:
  • isValidWord: Checks if a word exists in the dictionary.
  • transformWord: Performs the BFS to find the shortest transformation.
  • main: Handles user input and initializes the process.

Code Implementation

#include 
#include 
#include 
#include 

#define MAX_WORD_LENGTH 100
#define MAX_WORDS 1000

typedef struct Node {
    char word[MAX_WORD_LENGTH];
    int level; // Level of transformation
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front;
    Node *rear;
} Queue;

// Function declarations
Queue* createQueue();
void enqueue(Queue *q, char *word, int level);
Node* dequeue(Queue *q);
bool isEmpty(Queue *q);
bool isValidWord(char *word, char dictionary[][MAX_WORD_LENGTH], int dictSize);
void transformWord(char *beginWord, char *endWord, char dictionary[][MAX_WORD_LENGTH], int dictSize);

int main() {
    char dictionary[MAX_WORDS][MAX_WORD_LENGTH] = {
        "hit", "hot", "dot", "dog", "cog", "lot", "log"
    };
    char beginWord[MAX_WORD_LENGTH], endWord[MAX_WORD_LENGTH];

    printf("Enter the starting word: ");
    scanf("%s", beginWord);
    printf("Enter the ending word: ");
    scanf("%s", endWord);

    transformWord(beginWord, endWord, dictionary, 7);

    return 0;
}

// Create a new queue
Queue* createQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Enqueue a new node
void enqueue(Queue *q, char *word, int level) {
    Node *temp = (Node *)malloc(sizeof(Node));
    strcpy(temp->word, word);
    temp->level = level;
    temp->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
}

// Dequeue a node
Node* dequeue(Queue *q) {
    if (isEmpty(q)) return NULL;

    Node *temp = q->front;
    q->front = q->front->next;

    if (q->front == NULL) q->rear = NULL;
    return temp;
}

// Check if queue is empty
bool isEmpty(Queue *q) {
    return (q->front == NULL);
}

// Check if a word is valid in the dictionary
bool isValidWord(char *word, char dictionary[][MAX_WORD_LENGTH], int dictSize) {
    for (int i = 0; i < dictSize; i++) { if (strcmp(word, dictionary[i]) == 0) { return true; } } return false; } // Transform word using BFS void transformWord(char *beginWord, char *endWord, char dictionary[][MAX_WORD_LENGTH], int dictSize) { if (!isValidWord(endWord, dictionary, dictSize)) { printf("End word is not in the dictionary.\n"); return; } Queue *q = createQueue(); enqueue(q, beginWord, 1); // Start with the beginWord while (!isEmpty(q)) { Node *current = dequeue(q); char *word = current->word;
        int level = current->level;

        if (strcmp(word, endWord) == 0) {
            printf("Minimum number of transformations: %d\n", level);
            return;
        }

        // Generate next possible words
        for (int i = 0; word[i]; i++) {
            char originalChar = word[i];

            // Change each letter to every possible letter a-z
            for (char c = 'a'; c <= 'z'; c++) {
                word[i] = c;
                if (isValidWord(word, dictionary, dictSize)) {
                    enqueue(q, word, level + 1);
                }
            }
            word[i] = originalChar; // Restore original character
        }
        free(current);
    }
    printf("No transformation possible.\n");
}

Explanation of the Code

The program starts by defining the required data structures, namely the Node for the queue and the Queue itself. The BFS algorithm is implemented in the transformWord function, which:

1. Initializes the queue with the starting word.
2. Processes each word level-by-level, checking if it matches the target word.
3. Generates new words by changing one letter at a time and checks if they exist in the dictionary.
4. Enqueues valid words along with their transformation levels.
5. Finally, it prints the minimum number of transformations required.

Conclusion

This program effectively demonstrates how to solve the Word Ladder Problem using BFS in C. The pattern of using queues for traversing the transformation paths allows for an efficient search, ensuring the shortest path is found.