127.
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
int l = beginWord.length(), n = wordList.size(), i;
if(l <= || n <= || beginWord == endWord)
return ;
queue<string> q;
q.push(beginWord);
map<string, int> m;
m[beginWord] = ;
while(!q.empty())
{
string s = q.front();
q.pop();
for(i = ; i < l; i++)
{
for(char c = 'a'; c <= 'z'; c++)
{
string t = s;
t[i] = c;
if(wordList.find(t) != wordList.end() && m.find(t) == m.end())
{
m[t] = m[s] + ;
if(t == endWord)
return m[t];
q.push(t);
}
}
}
}
return ;
}
};
// ---------------------------
// BFS non-recursive method
// ---------------------------
//
// Using BFS instead of DFS is becasue the solution need the shortest transformation path.
//
// So, we can change every char in the word one by one, until find all possible transformation.
//
// Keep this iteration, we will find the shorest path.
//
// For example:
//
// start = "hit"
// end = "cog"
// dict = ["hot","dot","dog","lot","log","dit","hig", "dig"]
//
// +-----+
// +-------------+ hit +--------------+
// | +--+--+ |
// | | |
// +--v--+ +--v--+ +--v--+
// | dit | +-----+ hot +---+ | hig |
// +--+--+ | +-----+ | +--+--+
// | | | |
// | +--v--+ +--v--+ +--v--+
// +----> dot | | lot | | dig |
// +--+--+ +--+--+ +--+--+
// | | |
// +--v--+ +--v--+ |
// +----> dog | | log | |
// | +--+--+ +--+--+ |
// | | | |
// | | +--v--+ | |
// | +--->| cog |<-- + |
// | +-----+ |
// | |
// | |
// +----------------------------------+
//
// 1) queue <== "hit"
// 2) queue <== "dit", "hot", "hig"
// 3) queue <== "dot", "lot", "dig"
// 4) queue <== "dog", "log"
126.
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
class Solution {
public:
void buildTree(string beginWord, string endWord, unordered_set<string> &wordList, map<string, unordered_set<string>> &m)
{
map<string, int> level;
level[beginWord] = ;
queue<string> q;
q.push(beginWord);
int lvl = ;
while (!q.empty())
{
string s = q.front();
q.pop();
if (lvl && level[s] > lvl)
break;
bool found = false;
int l = s.length(), i;
for (i = ; i < l; i++)
{
string t = s;
for (char c = 'a'; c <= 'z'; c++)
{
t[i] = c;
if (t == endWord)
{
m[s].clear();
m[s].insert(endWord);
lvl = level[s];
found = true;
break;
}
else if (wordList.find(t) != wordList.end())
{
if (level.find(t) == level.end())
{
level[t] = level[s] + ;
m[s].insert(t);
q.push(t);
}
else if (level[t] == level[s] + )
{
m[s].insert(t);
}
}
}
if (found)
break;
}
}
}
int countnum = ;
void dfs(string endWord, vector<vector<string>> &ans, vector<string> &v, map<string, unordered_set<string>> &m, string s)
{
if (m.find(s) == m.end() && s == endWord)
{
ans.push_back(v);
return;
}
for (unordered_set<string>::iterator it = m[s].begin(); it != m[s].end(); it++)
{
v.push_back(*it);
dfs(endWord, ans, v, m, *it);
v.pop_back();
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
vector<vector<string>> ans;
int l = beginWord.length(), n = wordList.size();
if (l <= || n <= || beginWord == endWord)
return ans;
map<string, unordered_set<string>> m;
buildTree(beginWord, endWord, wordList, m);
vector<string> v;
v.push_back(beginWord);
map<string, bool> visit;
dfs(endWord, ans, v, m, beginWord);
return ans;
}
};
// Solution
//
// 1) Using BSF algorithm build a tree like below
// 2) Using DSF to parse the tree to the transformation path.
//
// For example:
//
// start = "hit"
// end = "cog"
// dict = ["hot","dot","dog","lot","log","dit","hig", "dig"]
//
// +-----+
// +-------------+ hit +--------------+
// | +--+--+ |
// | | |
// +--v--+ +--v--+ +--v--+
// | dit | +-----+ hot +---+ | hig |
// +--+--+ | +-----+ | +--+--+
// | | | |
// | +--v--+ +--v--+ +--v--+
// +----> dot | | lot | | dig |
// +--+--+ +--+--+ +--+--+
// | | |
// +--v--+ +--v--+ |
// +----> dog | | log | |
// | +--+--+ +--+--+ |
// | | | |
// | | +--v--+ | |
// | +--->| cog |<-- + |
// | +-----+ |
// | |
// | |
// +----------------------------------+