## Saturday, April 2, 2016

### LeetCode OJ - Word Ladder

Problem:

Analysis:

This is a simple graph search, nothing much to talk about except one trick that I owe Zhicheng. In order to build the graph to search, one naturally need to consider every pair of words to see if they're connected, that will lead to an $O(n^2)$ algorithm, but ...

Solution:

We can do that in $O(n + m)$ where $m$ is the actual number of links (assuming the length of the word is a constant). The key idea is put the words in a hash table, and then checking each possible children of a word by varying one letter at a time. For each node we will probe the hash table 26 x length of word times, but that is just a constant, so we will find all children in constant time, skipping the graph construction.

Code:

#include "stdafx.h"

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <queue>

using namespace std;

{
class Solution
{
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList)
{
int n = 0;
unordered_map<string, int> wordMap;
vector<string> strings;

for (unordered_set<string>::iterator wi = wordList.begin(); wi != wordList.end(); wi++)
{
strings.push_back(*wi);
wordMap.insert(pair<string, int>(*wi, n++));
}

wordMap.erase(beginWord);
wordMap.erase(endWord);
wordMap.insert(pair<string, int>(beginWord, n));
wordMap.insert(pair<string, int>(endWord, n + 1));
strings.push_back(beginWord);
strings.push_back(endWord);

queue<int> bfs_queue;

vector<bool> enqueued(n + 2);
vector<int> lengths(n + 2);
for (int i = 0; i < n; i++)
{
enqueued[i] = false;
lengths[i] = 0;
}

lengths[n] = 1;
enqueued[n] = true;
bfs_queue.push(n);

while (bfs_queue.size() > 0)
{
int current_id = bfs_queue.front();
bfs_queue.pop();
string current = strings[current_id];
int length = lengths[current_id];

for (int c = 0; c < current.length(); c++)
{
char backup = current[c];
for (char a = 'a'; a <= 'z'; a++)
{
current[c] = a;
unordered_map<string, int>::iterator probe = wordMap.find(current);
if (probe != wordMap.end())
{
int neighbor_id = probe->second;
if (neighbor_id == (n + 1))
{
return length + 1;
}
if (!enqueued[neighbor_id])
{
lengths[neighbor_id] = length + 1;
enqueued[neighbor_id] = true;
bfs_queue.push(neighbor_id);
}
}
}
current[c] = backup;
}
}

return 0;
}
};
}

}