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 <iostream>
2#include <vector>
3#include <unordered_set>
4#include <queue>
5
6using namespace std;
7
8bool oneLetterDifference(const string &s1, const string &s2) {
9 int count = 0;
10 for (int i = 0; i < s1.length(); ++i) {
11 if (s1[i] != s2[i] && ++count > 1) return false;
12 }
13 return count == 1;
14}
15
16int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
17 unordered_set<string> wordSet(wordList.begin(), wordList.end());
18 if (wordSet.find(endWord) == wordSet.end()) return 0;
19 queue<string> q;
20 q.push(beginWord);
21 int ladder = 1;
22
23 while (!q.empty()) {
24 int levelSize = q.size();
25 for (int i = 0; i < levelSize; ++i) {
26 string current = q.front(); q.pop();
27 for (int j = 0; j < current.length(); ++j) {
28 string temp = current;
29 for (char c = 'a'; c <= 'z'; ++c) {
30 temp[j] = c;
31 if (temp == endWord) return ladder + 1;
32 if (wordSet.find(temp) != wordSet.end()) {
33 q.push(temp);
34 wordSet.erase(temp);
35 }
36 }
37 }
38 }
39 ladder++;
40 }
41 return 0;
42}
43
44int main() {
45 vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
46 cout << ladderLength("hit", "cog", wordList) << endl;
47 return 0;
48}This C++ implementation utilizes an unordered_set to allow efficient checks and deletions. During the BFS process, on transforming a word, if it exists in the word set, it gets queued for further exploration. A crucial update when a transformation leads to endWord increments the ladder length count, as it signifies another valid step in our shortest path traversal.