Solution to Word Ladder II by LeetCode

Question: https://oj.leetcode.com/problems/word-ladder-ii/

Question Name: Word Ladder II

class Solution:

# @param start, a set of string

# @return two dictionaries

def _buildSig(self, contents):

sig = {} # Records the signatures for each string

bucket = {} # Records the strings with each signature

for string in contents:

sig[string] = []

for index in xrange(len(string)):

tempSig = string[:index] + "*" + string[index+1:]

sig[string].append(tempSig)

if tempSig not in bucket: bucket[tempSig] = []

bucket[tempSig].append(string)

return sig, bucket

# @param start, a string

# @param end, a string

# @param dict, a set of string

# @return a list of lists of string

def findLadders(self, start, end, dict):

# Build the graph.

# Two nodes (whose value is the string in dict), are connected if

# they have one same signature or more.

sig, bucket = self._buildSig(set([start, end]) | dict)

result = []

accessed = {}

for string in dict: accessed[string] = False

accessed[start] = True

# Travel the graph in breadth-first search.

currentLayer = [[start]]

steps = 1

while len(currentLayer) != 0 and len(result) == 0:

steps += 1

nextLayer = []

accessedTemp = []

for intermediate in currentLayer:

signatures = sig[intermediate[-1]]

for signature in signatures:

for nextLayerCandidate in bucket[signature]:

# Transformation from start to end finished.

if nextLayerCandidate == end:

result.append(intermediate + [end])

continue

# Accessed before. Not to access again.

if accessed[nextLayerCandidate]:

continue

# We cannot set the accessed flag instantly here.

# The other same-deep nodes(stirng) also have the

# right to jump to this node(string).

accessedTemp.append(nextLayerCandidate)

nextLayer.append(intermediate + [nextLayerCandidate])

for item in accessedTemp: accessed[item] = True

currentLayer = nextLayer

return result

One Reply to “Solution to Word Ladder II by LeetCode”

Tried to maintain a small memory profile through recursive backtracing, which requires a DFS to conduct. So, doing a BFS first to collect necessary info to guide the following DFS. Therefore, only a single vector is necessary for tracking all possible shortest path.

#include <unordered_map>

#include <string>

#include <vector>

#include <unordered_set>

#include <queue>

using namespace std;

class SolutionWordLadder2 {

private:

void aux(vector<vector<string>>& ans, vector<string>& vec, unordered_map<string, std::pair<vector<string>, int>>& g, const string& start, const string& end, int order) {

vec[order] = start;

if (end == start) {

ans.push_back(std::move(vector<string>(vec.begin(), vec.begin() + order + 1)));

return;

}

for (auto& str : g[start].first)

if (g[str].second == order + 1)

this->aux(ans, vec, g, str, end, order + 1);

public:

vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {

vector<vector<string>> ans;

unordered_map<string, std::pair<vector<string>, int>> g;

dict.emplace(end);

size_t len = start.length();

char old_char = 0;

string str, key;

queue<string> q;

q.push(start);

while (false == q.empty()) {

key = std::move(q.front()); q.pop();

if (key == end) break;

str = key;

if (start == key)

g.emplace(key, std::make_pair(vector<string>(), 0));

for (size_t i = 0; i < len; ++i) {

for (char j = 'a'; j <= 'z'; ++j) {

if (j == str[i])continue;

old_char = str[i];

str[i] = j;

if (dict.end() != dict.find(str)) {

if (g.end() == g.find(str) || g[str].second == g[key].second + 1) {

if (g.end() == g.find(str)) {

q.push(str);

g.emplace(str, std::make_pair(vector<string>(), g[key].second + 1));

g[key].first.push_back(str);

str[i] = old_char;

vector<string> vec(dict.size() + 2);

this->aux(ans, vec, g, start, end, 0);

return ans;

};

One Reply to “Solution to Word Ladder II by LeetCode”

Leave a Reply Cancel reply