This problem looks busy at first, but the accepted solution is built around one steady invariant. For 127. Word Ladder, the solution in this repository is mainly a graph traversal solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal.
The notes already sitting in the source point us in the right direction:
- Graph, BFS
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are connected, ladderLength, visited, visitWordNode, visited_begin.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- Substring checks are convenient but not free, so they are part of the real complexity story.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Graph, BFS
02//Runtime: 652 ms, faster than 27.76% of C++ online submissions for Word Ladder.
03//Memory Usage: 14.3 MB, less than 47.16% of C++ online submissions for Word Ladder.
04class Solution {
05public:
06 bool connected(string& s1, string& s2){
07 int m = s1.size();
08 int n = s2.size();
09 if(m != n) return -1;
10
11 int count = 0;
12 for(int i = 0; i < m; ++i){
13 if(s1[i] != s2[i]){
14 ++count;
15 if(count > 1) return false;
16 }
17 }
18 return count == 1;
19 };
20
21 int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
22 auto it = find(wordList.begin(), wordList.end(), beginWord);
23 int start;
24 if(it == wordList.end()){
25 wordList.push_back(beginWord);
26 start = wordList.size()-1;
27 }else{
28 start = it - wordList.begin();
29 }
30
31 it = find(wordList.begin(), wordList.end(), endWord);
32 if(it == wordList.end()) return 0;
33 int end = it - wordList.begin();
34
35 // cout << "start: " << start << ", end: " << end << endl;
36
37 int n = wordList.size();
38
39 vector<vector<int>> adjList(n);
40
41 for(int i = 0; i < n; ++i){
42 for(int j = i+1; j < n; ++j){
43 if(connected(wordList[i], wordList[j])){
44 adjList[i].push_back(j);
45 adjList[j].push_back(i);
46 // cout << wordList[i] << " <-> " << wordList[j] << endl;
47 }
48 }
49 }
50
51 //BFS
52 queue<int> q;
53 int cur;
54 int level = 1; //the length of the path containing only start
55 vector<bool> visited(n, false);
56 q.push(start);
57 visited[start] = true;
58
59 while(!q.empty()){
60 int levelSize = q.size();
61 // cout << "level: " << level << ", levelSize: " << levelSize << endl;
62
63 while(levelSize-- > 0){
64 cur = q.front(); q.pop();
65 // cout << wordList[cur] << endl;
66
67 if(cur == end){
68 return level;
69 }
70
71 for(int nei : adjList[cur]){
72 if(!visited[nei]){
73 visited[nei] = true;
74 q.push(nei);
75 }
76 }
77 }
78
79 ++level;
80 }
81
82 //cannot find a path
83 return 0;
84 }
85};
86
87//Approach 1: Breadth First Search
88//Runtime: 156 ms, faster than 71.95% of C++ online submissions for Word Ladder.
89//Memory Usage: 23.9 MB, less than 21.59% of C++ online submissions for Word Ladder.
90//time: O(M^2*N), space: O(M^2*N)
91//M is the length of each word and N is the total number of words in the input word list
92class Solution {
93public:
94 int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
95 auto it = find(wordList.begin(), wordList.end(), beginWord);
96 int start;
97 if(it == wordList.end()){
98 wordList.push_back(beginWord);
99 start = wordList.size()-1;
100 }else{
101 start = it - wordList.begin();
102 }
103
104 it = find(wordList.begin(), wordList.end(), endWord);
105 if(it == wordList.end()) return 0;
106 int end = it - wordList.begin();
107
108 int m = beginWord.size();
109 int n = wordList.size();
110 //(generic word, id in wordList)
111 unordered_map<string, vector<int>> allComboDict;
112
113 for(int i = 0; i < n; ++i){
114 for(int j = 0; j < m; ++j){
115 //replace ith char with '*'
116 string newword = wordList[i].substr(0, j) + '*' + wordList[i].substr(j+1);
117 allComboDict[newword].push_back(i);
118 }
119 }
120
121 //BFS
122 queue<int> q;
123 int cur;
124 int level = 1; //the length of the path containing only start
125 vector<bool> visited(n, false);
126 q.push(start);
127 visited[start] = true;
128
129 while(!q.empty()){
130 int levelSize = q.size();
131 // cout << "level: " << level << ", levelSize: " << levelSize << endl;
132
133 while(levelSize-- > 0){
134 cur = q.front(); q.pop();
135 // cout << wordList[cur] << endl;
136
137 if(cur == end){
138 return level;
139 }
140
141 //iterate all char and build its generic word
142 for(int i = 0; i < m; ++i){
143 string newword = wordList[cur].substr(0, i) + '*' + wordList[cur].substr(i+1);
144
145 //use this generic word to find its neighbor
146 for(int nei : allComboDict[newword]){
147 if(!visited[nei]){
148 visited[nei] = true;
149 q.push(nei);
150 }
151 }
152 }
153 }
154
155 ++level;
156 }
157
158 //cannot find a path
159 return 0;
160 }
161};
162
163//Approach 2: Bidirectional Breadth First Search
164//Runtime: 120 ms, faster than 84.54% of C++ online submissions for Word Ladder.
165//Memory Usage: 24.2 MB, less than 21.02% of C++ online submissions for Word Ladder.
166//time: O(M^2*N), space: O(M^2*N)
167class Solution {
168public:
169 int m, n;
170 //(generic word, id in wordList)
171 unordered_map<string, vector<int>> allComboDict;
172
173 int visitWordNode(vector<string>& wordList,
174 queue<int>& q, vector<int>& visited, vector<int>& visited_other){
175 int cur = q.front(); q.pop();
176 // cout << wordList[cur] << " : " << visited[cur] << endl;
177
178 for(int i = 0; i < m; ++i){
179 string newword = wordList[cur].substr(0, i) + '*' + wordList[cur].substr(i+1);
180
181 for(int& nei : allComboDict[newword]){
182 if(visited_other[nei] > 0){
183 //use visited[cur] to retrieve cur's level
184 // cout << wordList[nei] << " : " << visited_other[nei] << endl;
185 return visited[cur] + visited_other[nei];
186 }
187
188 if(visited[nei] < 0){
189 visited[nei] = visited[cur]+1;
190 q.push(nei);
191 }
192 }
193 }
194
195 return -1;
196 };
197
198 int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
199 auto it = find(wordList.begin(), wordList.end(), beginWord);
200 int start;
201 if(it == wordList.end()){
202 wordList.push_back(beginWord);
203 start = wordList.size()-1;
204 }else{
205 start = it - wordList.begin();
206 }
207
208 it = find(wordList.begin(), wordList.end(), endWord);
209 if(it == wordList.end()) return 0;
210 int end = it - wordList.begin();
211
212 m = beginWord.size();
213 n = wordList.size();
214
215 for(int i = 0; i < n; ++i){
216 for(int j = 0; j < m; ++j){
217 //replace ith char with '*'
218 string newword = wordList[i].substr(0, j) + '*' + wordList[i].substr(j+1);
219 allComboDict[newword].push_back(i);
220 }
221 }
222
223 queue<int> q_begin, q_end;
224 q_begin.push(start);
225 q_end.push(end);
226
227 //-1 for not visited, >= 0 for its level
228 vector<int> visited_begin(n, -1), visited_end(n, -1);
229 /*
230 we want to find the length of the sequence,
231 so both "start" and "end" take one place
232 */
233 visited_begin[start] = 1;
234 visited_end[end] = 1;
235
236 int ans;
237
238 while(!q_begin.empty() && !q_end.empty()){
239 // cout << "forward: " << endl;
240 ans = visitWordNode(wordList, q_begin, visited_begin, visited_end);
241 if(ans > -1) return ans;
242
243 // cout << "backward: " << endl;
244 ans = visitWordNode(wordList, q_end, visited_end, visited_begin);
245 if(ans > -1) return ans;
246 }
247
248 return 0;
249 }
250};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.