Problem: 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 transformed word must exist in the word list.
Example:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog" with 5 words.
Approach: If you look, this problem is more like getting the shortest length path in a acyclic directed unweighted graph so we can use BFS(using queue) here. We can assume the word1 and word2 are connected if one letter change can transform word1 to word2.
Now the problem is how to define edges efficiently. What we can do is we can replace characters at i = 0 ... n one by one with a special character say '#' and the new word "...#..." can become the key in the hash and the original word can be added in the value. Lets take an example (taken from geeksforgeeks) -
{ABCD, EBAD, EBCD, XYZA}
Hash -
#BCD -> [ABCD, EBCD]
A#CD -> [ABCD]
AB#D -> [ABCD]
ABC# -> [ABCD]
...
...
...
Implementation in C#:
public int LadderLength(string beginWord, string endWord, IList<string> wordList)
{
if (wordList?.Count == 0 || !wordList.Contains(endWord) || beginWord.Length != endWord.Length || beginWord == endWord)
{
return 0;
}
if (wordList.Contains(beginWord))
{
wordList.Remove(beginWord);
}
Dictionary<string, List<int>> wordGraph = this.BuildWordGraph(wordList);
List<int> beginWordNeighbors = this.GetBeginWordNeighbors(beginWord, wordGraph);
if (beginWordNeighbors?.Count == 0)
{
return 0;
}
Queue<int> queue = new Queue<int>();
HashSet<int> visited = new HashSet<int>();
int dist = 1;
foreach (int neighbor in beginWordNeighbors)
{
if (!visited.Contains(neighbor))
{
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
while (queue.Count > 0)
{
int size = queue.Count;
for (int i = 0; i < size; ++i)
{
int currIndex = queue.Dequeue();
if (wordList[currIndex] == endWord)
{
return dist + 1;
}
this.AddNeighborsToQueueIfNotVisited(wordList[currIndex], queue, wordGraph, visited);
}
++dist;
}
return 0;
}
private void AddNeighborsToQueueIfNotVisited(string word, Queue<int> queue, Dictionary<string, List<int>> wordGraph, HashSet<int> visited)
{
char[] wordArr = word.ToCharArray();
for (int i = 0; i < wordArr.Length; ++i)
{
char tempChar = wordArr[i];
wordArr[i] = '#';
string key = new string(wordArr);
if (wordGraph.ContainsKey(key))
{
List<int> indices = wordGraph[key];
foreach (int index in indices)
{
if (!visited.Contains(index))
{
visited.Add(index);
queue.Enqueue(index);
}
}
}
wordArr[i] = tempChar;
}
}
private List<int> GetBeginWordNeighbors(string beginWord, Dictionary<string, List<int>> wordGraph)
{
List<int> neighbors = new List<int>();
char[] beginWordArr = beginWord.ToCharArray();
for (int i = 0; i < beginWordArr.Length; ++i)
{
char tempChar = beginWordArr[i];
beginWordArr[i] = '#';
string key = new string(beginWordArr);
if (wordGraph.ContainsKey(key))
{
neighbors.AddRange(wordGraph[key]);
}
beginWordArr[i] = tempChar;
}
return neighbors;
}
private Dictionary<string, List<int>> BuildWordGraph(IList<string> wordList)
{
Dictionary<string, List<int>> wordGraph = new Dictionary<string, List<int>>();
for (int i = 0; i < wordList.Count; ++i)
{
char[] word = wordList[i].ToCharArray();
for (int j = 0; j < word.Length; ++j)
{
char tempChar = word[j];
word[j] = '#';
string key = new string(word);
if (!wordGraph.ContainsKey(key))
{
wordGraph[key] = new List<int>();
}
wordGraph[key].Add(i);
word[j] = tempChar;
}
}
return wordGraph;
}
Complexity: O(m^2 * n) where m is the number of words and n is number of chars in the word.
No comments:
Post a Comment