Lintcode: Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Have you met this question in a real interview? 

Yes

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Tags Expand 

Breadth First Search

Codes and thought reference:;

http://bangbingsyb.blogspot.com/2014/11/leetcode-word-ladder-i-ii.html

s1: insert end string into dict
s2: BFS adjacent nodes from start string

About adjacent node: Here is to get string that has only one different digit;
Compare length of the string to get adjacent strings is w
One way is to search the whole dictionary and get string with only one different digit O(n*w)
Second way is to get all strings with one different digit O(26*w)
When dictionary is large, we have to use second way

Time: O(E)
Space: O(V)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public: /** * @param start, a string * @param end, a string * @param dict, a set of string * @return an integer */ int ladderLength(string start, string end, unordered_set<string> &dict) { // write your code here dict.insert(end); queue<pair<string, int> > Q; Q.push(make_pair(start, 1)); while(!Q.empty()){ string s = Q.front().first; int len = Q.front().second; Q.pop(); if(s == end) return len; findNeibors(Q, s, len, dict); } return 0; } void findNeibors(queue<pair<string, int> > &Q, string s, int len, unordered_set<string> &dict){ vector<string> neibors; for(int i = 0; i < s.length(); i++){ char c = s[i]; for(int j = 0; j < 26; j++){ s[i] = 'a' + j; if(s[i] == c) continue; if(dict.count(s)) { neibors.push_back(s); dict.erase(s); } } s[i] = c; //DON"T FORGET } for(int i = 0; i < neibors.size(); i++){ Q.push(make_pair(neibors[i], len + 1)); } } };

Lintcode second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

class Solution { public: /** * @param start, a string * @param end, a string * @param dict, a set of string * @return an integer */ int ladderLength(string start, string end, unordered_set<string> &dict) { // write your code here queue<string> Q; if(start == "") return 0; Q.push(start); int size = 1; int curLevel = 1; while(!Q.empty()){ string cur = Q.front(); Q.pop(); size--; if(cur == end) return curLevel; //find neighbors and add them to Q for(int i = 0; i < cur.size(); i++){ char c = cur[i]; for(int j = 0; j < 26; j++){ if(c == 'a' + j) continue; cur[i] = 'a' + j; if(dict.count(cur)) { Q.push(cur); dict.erase(cur); //Don't forget } } cur[i] = c; //dong't forget } //update level if(size == 0){ size = Q.size(); curLevel++; } } return 0; } };