Sponsored
Sponsored
This approach leverages Breadth First Search (BFS), where each word is a node in the graph, and an edge exists between two nodes if they differ by exactly one letter. The goal is to find the shortest path from beginWord to endWord.
Start BFS from the beginWord, exploring transformations by changing each letter and checking if the new word exists in the set of available words. Polished implementation should consider preprocessing the word list for efficient lookup.
Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case.
Space Complexity: O(N), where N is the number of nodes (words) we store in the queue.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4#include <stdlib.h>
5
6#define MAX_WORDS 5000
7#define WORD_LENGTH 10
8
9bool oneLetterDifference(char* word1, char* word2) {
10 int count = 0;
11 for (int i = 0; i < strlen(word1); i++) {
12 if (word1[i] != word2[i]) count++;
13 if (count > 1) return false;
14 }
15 return count == 1;
16}
17
18int ladderLength(char *beginWord, char *endWord, char **wordList, int wordListSize) {
19 bool visited[MAX_WORDS] = { false };
20 char* queue[MAX_WORDS];
21 int front = 0, rear = 0;
22 int levels = 1;
23
24 queue[rear++] = beginWord;
25
26 while (front < rear) {
27 int currLevelSize = rear - front;
28 for (int i = 0; i < currLevelSize; i++) {
29 char* current = queue[front++];
30
31 if (strcmp(current, endWord) == 0) {
32 return levels;
33 }
34
35 for (int j = 0; j < wordListSize; j++) {
36 if (!visited[j] && oneLetterDifference(current, wordList[j])) {
37 visited[j] = true;
38 queue[rear++] = wordList[j];
39 }
40 }
41 }
42 levels++;
43 }
44
45 return 0;
46}
47
48int main() {
49 char* wordList[] = {"hot","dot","dog","lot","log","cog"};
50 int wordListSize = sizeof(wordList)/sizeof(wordList[0]);
51 printf("%d\n", ladderLength("hit", "cog", wordList, wordListSize));
52 return 0;
53}This C solution uses BFS to navigate from the beginWord to the endWord. It maintains a queue for exploration, marking words as visited to prevent revisiting them. The function oneLetterDifference checks if two words differ by exactly one letter, crucial for establishing edges in the BFS traversal.