Posts tagged as “Bidirectional BFS”

花花酱 8 Puzzles – Bidirectional A* vs Bidirectional BFS

By zxi on April 30, 2019

8 Puzzles # nodes expended of 1000 solvable instances

Conclusion:

Nodes expended: BiDirectional A* << A* (Manhattan) <= Bidirectional BFS < A* Hamming << BFS
Running time: BiDirectional A* < Bidirectional BFS <= A* (Manhattan) < A* Hamming << BFS

Code:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

# Author: Huahua

from collections import deque

import heapq

import numpy as np

import random

import sys

N = 3

def Manhattan(s1, s2):

dist = 0

for i1, d in enumerate(s1):

i2 = s2.index(d)

x1 = i1 % N

y1 = i1 // N

x2 = i2 % N

y2 = i2 // N

dist += abs(x1 - x2) + abs(y1 - y2)

return dist

def Hamming(s1, s2):

return sum(x != y for x, y in zip(s1, s2))

class Node:

dirs = [0, -1, 0, 1, 0]

def __init__(self, state, parent = None, h = 0):

self.state = state

self.parent = parent

self.g = parent.g + 1 if parent else 0

self.h = h

self.f = self.g + self.h

def getMoves(self):

moves = []

index = self.state.index(0)

x = index % N

y = index // N

for i in range(4):

tx = x + Node.dirs[i]

ty = y + Node.dirs[i + 1]

if tx < 0 or ty < 0 or tx == N or ty == N:

continue

i = ty * N + tx

move = list(self.state)

move[index] = move[i]

move[i] = 0

moves.append(tuple(move))

return moves

def print(self):

print(np.reshape(self.state, (N, N)))

def __lt__(self, other):

return self.f < other.f

def AStarSearch(start_state, end_state, heuristic):

def h(s):

return heuristic(s, end_state)

q = []

s = Node(start_state, h=h(start_state))

heapq.heappush(q, s)

opened = {s.state : s.f}

closed = dict()

while q:

n = heapq.heappop(q)

if n.state == end_state:

return n, len(opened), len(closed)

if n.state in closed: continue

closed[n.state] = n.f

for move in n.getMoves():

node = Node(move, n, h(move))

if move in opened and opened[move] <= node.f: continue

opened[node.state] = node.f

heapq.heappush(q, node)

return None, len(opened), len(closed)

def BFS(start_state, end_state):

q = deque()

q.append(Node(start_state))

opened = set(start_state)

closed = 0

while q:

n = q.popleft()

if n.state == end_state:

return n, len(opened), closed

closed += 1

for move in n.getMoves():

if move in opened: continue

opened.add(move)

q.append(Node(move, n))

return None, len(opened), closed

def getRootNode(n):

return getRootNode(n.parent) if n.parent else n

def BidirectionalBFS(start_state, end_state):

def constructPath(p, o):

while o:

t = o.parent

o.parent = p

p, o = o, t

return p

ns = Node(start_state)

ne = Node(end_state)

q = [deque([ns]), deque([ne])]

opened = [{start_state : ns}, {end_state: ne}]

closed = [0, 0]

while q[0]:

l = len(q[0])

while l > 0:

p = q[0].popleft()

closed[0] += 1

for move in p.getMoves():

n = Node(move, p)

if move in opened[1]:

o = opened[1][move]

if getRootNode(n).state == end_state:

o, n = n, o

n = constructPath(n, o.parent)

return n, len(opened[0]) + len(opened[1]), closed[0] + closed[1]

if move in opened[0]: continue

opened[0][move] = n

q[0].append(n)

l -= 1

q.reverse()

opened.reverse()

closed.reverse()

return None, len(opened[0]) + len(opened[1]), closed[0] + closed[1]

def print_path(n):

if not n: return

print_path(n.parent)

n.print()

def solvable(state):

inv = 0

for i in range(N*N):

for j in range(i + 1, N*N):

if all((state[i] > 0, state[j] > 0, state[i] > state[j])):

inv += 1

return inv % 2 == 0

if __name__ == '__main__':

s = [1, 2, 3, 4, 5, 6, 7, 8, 0]

e = [1, 2, 3, 4, 5, 6, 7, 8, 0]

i = 0

while True:

random.shuffle(s)

if not solvable(s): continue

n1, opened1, closed1 = AStarSearch(tuple(s), tuple(e), heuristic=Manhattan)

n2, opened2, closed2 = AStarSearch(tuple(s), tuple(e), heuristic=Hamming)

n3, opened3, closed3 = BFS(tuple(s), tuple(e))

n4, opened4, closed4 = BidirectionalBFS(tuple(s), tuple(e))

print("%d\t%d\t%d\t%d" % (closed1, closed2, closed3, closed4))

sys.stdout.flush()

# print("A*")

# print_path(n1)

# print('---------------')

# print("BFS")

# print_path(n3)

# print('---------------')

# print("Bi-BFS")

# print_path(n4)

# print('---------------')

i += 1

if i == 1000: break

C++ Version

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

#include <algorithm>

#include <array>

#include <chrono>

#include <deque>

#include <functional>

#include <iostream>

#include <memory>

#include <queue>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using chrono::high_resolution_clock;

constexpr int N = 3;

constexpr int dirs[] = {0, 1, 0, -1, 0};

struct Node;

typedef string State;

typedef shared_ptr<Node> NodePtr;

typedef function<int(const State& s, const State& t)> Heuristic;

struct Node {

Node(State s, NodePtr p = nullptr, int h = 0)

: s(s), p(p), h(h), g(p ? p->g + 1 : 0), f(this->h + g) {}

vector<State> GetNextStates() const {

vector<State> states;

int index = find(s.begin(), s.end(), '0') - s.begin();

int x = index % N;

int y = index / N;

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx == N || ty == N) continue;

int new_index = ty * N + tx;

State next(s);

next[index] = s[new_index];

next[new_index] = '0';

states.push_back(move(next));

}

return states;

}

NodePtr p;

int h;

int g;

int f;

State s;

};

bool Sovlable(const State& s) {

int inv_count = 0;

for (int i = 0; i < N * N; ++i) {

for (int j = i + 1; j < N * N; ++j) {

if (s[i] != '0' && s[j] != '0' && s[i] > s[j]) {

++inv_count;

}

return inv_count % 2 == 0;

}

NodePtr GetRoot(NodePtr n) { return n->p ? GetRoot(n->p) : n; }

NodePtr WirePath(NodePtr p, NodePtr n) {

while (n) {

NodePtr t = n->p;

n->p = p;

p = n;

n = t;

}

return p;

}

void ConstructPath(NodePtr node, vector<State>* path) {

while (node) {

path->push_back(node->s);

node = node->p;

}

reverse(path->begin(), path->end());

}

class Solver {

public:

virtual bool Solve(State start, State target, vector<State>* path,

int* opened, int* closed) = 0;

};

class BFSSolver : public Solver {

public:

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

int expended = 0;

unordered_set<string> seen;

deque<NodePtr> q{make_shared<Node>(start)};

while (!q.empty()) {

auto cur = q.front();

q.pop_front();

++expended;

if (cur->s == target) {

ConstructPath(cur, path);

*opened = seen.size();

*closed = expended;

return true;

}

for (const auto& s : cur->GetNextStates()) {

auto r = seen.insert(s);

if (!r.second) continue;

q.push_back(make_shared<Node>(s, cur));

}

return false;

}

};

class BidirectionalBFSSolver : public Solver {

public:

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

auto start_node = make_shared<Node>(start);

auto target_node = make_shared<Node>(target);

unordered_map<string, NodePtr> seen0{{start, start_node}};

unordered_map<string, NodePtr> seen1{{target, target_node}};

deque<NodePtr> q0{start_node};

deque<NodePtr> q1{target_node};

int expended = 0;

while (!q0.empty()) {

size_t size = q0.size();

while (size--) {

auto cur = q0.front();

q0.pop_front();

++expended;

for (const auto& s : cur->GetNextStates()) {

auto n = make_shared<Node>(s, cur);

auto it = seen1.find(s);

if (it != seen1.end()) {

auto p = it->second;

if (GetRoot(n)->s == target) swap(n, p);

n = WirePath(n, p->p);

ConstructPath(n, path);

*opened = seen0.size() + seen1.size();

*closed = expended;

return true;

}

if (seen0.count(s)) continue;

seen0[s] = n;

q0.push_back(n);

}

if (q1.size() < q0.size()) {

swap(q0, q1);

swap(seen0, seen1);

}

return false;

}

private:

};

struct NodeCompare : public binary_function<NodePtr, NodePtr, bool> {

bool operator()(const NodePtr& x, const NodePtr& y) const {

return x->f > y->f;

}

};

int ManhattanDistance(const State& s, const State& t) {

int h = 0;

for (int i1 = 0; i1 < N * N; ++i1) {

int i2 = t.find(s[i1]);

int x1 = i1 % N;

int y1 = i1 / N;

int x2 = i2 % N;

int y2 = i2 / N;

h += abs(x1 - x2) + abs(y1 - y2);

}

return h;

}

int HammingDistance(const State& s, const State& t) {

int h = 0;

for (size_t i = 0; i < s.size(); ++i) {

if (s[i] != t[i]) ++h;

}

return h;

}

class AStarSolver : public Solver {

public:

explicit AStarSolver(Heuristic heuristic) : heuristic_(heuristic) {}

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

unordered_map<string, NodePtr> o;

unordered_set<string> c;

priority_queue<NodePtr, vector<NodePtr>, NodeCompare> q;

q.emplace(new Node(start, nullptr, heuristic_(start, target)));

while (!q.empty()) {

auto cur = q.top();

q.pop();

if (cur->s == target) {

ConstructPath(cur, path);

*opened = o.size();

*closed = c.size();

return true;

}

if (!c.insert(cur->s).second) continue;

for (const auto& s : cur->GetNextStates()) {

auto it = o.find(s);

auto n = make_shared<Node>(s, cur, heuristic_(s, target));

if (it != o.end() && n->f >= it->second->f) continue;

o[s] = n;

q.push(n);

}

return false;

}

private:

Heuristic heuristic_;

};

class BiAStarSolver : public Solver {

public:

explicit BiAStarSolver(Heuristic heuristic) : heuristic_(heuristic) {}

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

unordered_map<string, NodePtr> o0, o1;

unordered_map<string, NodePtr> c0, c1;

priority_queue<NodePtr, vector<NodePtr>, NodeCompare> q0, q1;

q0.emplace(new Node(start, nullptr, heuristic_(start, target)));

q1.emplace(new Node(target, nullptr, heuristic_(target, start)));

bool farward = true;

while (!q0.empty()) {

auto size = q0.size();

while (size--) {

auto cur = q0.top();

q0.pop();

if (c0.count(cur->s)) continue;

c0[cur->s] = cur;

if (c1.count(cur->s)) {

auto p = c1[cur->s];

if (GetRoot(cur)->s == target) swap(cur, p);

cur = WirePath(cur, p->p);

ConstructPath(cur, path);

*opened = o0.size() + o1.size();

*closed = c0.size() + c1.size();

return true;

}

for (const auto& s : cur->GetNextStates()) {

auto it = o0.find(s);

auto n = make_shared<Node>(s, cur,

heuristic_(s, farward ? target : start));

if (it != o0.end() && n->f >= it->second->f) continue;

o0[s] = n;

q0.push(n);

}

if (q1.size() < q0.size()) {

swap(q0, q1);

swap(c0, c1);

swap(o0, o1);

farward = !farward;

}

return false;

}

private:

Heuristic heuristic_;

};

bool VerifyPath(const vector<State>& path, const State& s, const State& t) {

if (path.empty()) return false;

if (path.front() != s || path.back() != t) return false;

for (size_t i = 1; i < path.size(); ++i) {

Node n(path[i - 1]);

auto states = n.GetNextStates();

if (find(begin(states), end(states), path[i]) == end(states)) {

return false;

}

return true;

}

void StatisticsMode() {

State s{"123456780"};

State t{"123456780"};

vector<unique_ptr<Solver>> solvers;

solvers.emplace_back(new BFSSolver);

solvers.emplace_back(new AStarSolver(HammingDistance));

solvers.emplace_back(new AStarSolver(ManhattanDistance));

solvers.emplace_back(new BidirectionalBFSSolver);

solvers.emplace_back(new BiAStarSolver(ManhattanDistance));

for (int i = 0; i < 1000;) {

random_shuffle(s.begin(), s.end());

if (!Sovlable(s)) continue;

++i;

for (auto& solver : solvers) {

vector<State> path;

int opened;

int closed;

auto t0 = high_resolution_clock::now();

bool sovlable = solver->Solve(s, t, &path, &opened, &closed);

auto t1 = high_resolution_clock::now();

if (!VerifyPath(path, s, t)) {

cerr << "Invalid path!" << endl;

return;

}

auto time_span = chrono::duration_cast<chrono::duration<double>>(t1 - t0);

cout << closed << "\t" << time_span.count() * 1000 << "\t";

}

cout << endl;

}

int main() { StatisticsMode(); }

花花酱 LeetCode 752. Open the Lock

By zxi on December 25, 2017

Problem:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Output: 6

Explanation:

A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,

because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"

Output: 1

Explanation:

We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

Output: -1

Explanation:

We can't reach the target without getting stuck.

Example 4:

1 2	Input: deadends = ["0000"], target = "8888" Output: -1

Note:

The length of deadends will be in the range [1, 500].
target will not be in the list deadends.
Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

题目大意：

给你一个4位密码锁，0可以转到1和9，1可以转到0和2，。。。，9可以转到0和8。

另外给你一些死锁的密码，比如1234，一但转到任何一个死锁的密码，锁就无法再转动了。

给你一个目标密码，问你最少要转多少次才能从0000转到目标密码。

Solution:

C++

// Author: Huahua

// Runtime: 133 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

const string start = "0000";

unordered_set<string> dead(deadends.begin(), deadends.end());

if (dead.count(start)) return -1;

if (start == target) return 0;

queue<string> q;

unordered_set<string> visited{start};

int steps = 0;

q.push(start);

while (!q.empty()) {

++steps;

const int size = q.size();

for (int i = 0; i < size; ++i) {

const string curr = q.front();

q.pop();

for (int i = 0; i < 4; ++i)

for (int j = -1; j <= 1; j += 2) {

string next = curr;

next[i] = (next[i] - '0' + j + 10) % 10 + '0';

if (next == target) return steps;

if (dead.count(next) || visited.count(next)) continue;

q.push(next);

visited.insert(next);

}

return -1;

}

};

C++ / Bidirectional BFS

// Author: Huahua

// Runtime: 32 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

const string start = "0000";

unordered_set<string> dead(deadends.begin(), deadends.end());

if (dead.count(start)) return -1;

if (target == start) return 0;

queue<string> q1;

queue<string> q2;

unordered_set<string> v1{start};

unordered_set<string> v2{target};

int s1 = 0;

int s2 = 0;

q1.push(start);

q2.push(target);

while (!q1.empty() && !q2.empty()) {

if (!q1.empty()) ++s1;

const int size = q1.size();

for (int i = 0; i < size; ++i) {

const string curr = q1.front();

q1.pop();

for (int i = 0; i < 4; ++i)

for (int j = -1; j <= 1; j += 2) {

string next = curr;

next[i] = (next[i] - '0' + j + 10) % 10 + '0';

if (v2.count(next)) return s1 + s2;

if (dead.count(next) || v1.count(next)) continue;

q1.push(next);

v1.insert(next);

}

swap(q1, q2);

swap(v1, v2);

swap(s1, s2);

}

return -1;

}

};

C++ / Bidirectional BFS / int state / Array

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

constexpr int kMaxN = 10000;

const vector<int> bases{1, 10, 100, 1000};

const int start = 0;

const int goal = stoi(target);

queue<int> q1;

queue<int> q2;

vector<int> v1(kMaxN, 0);

vector<int> v2(kMaxN, 0);

for (const string& deadend : deadends)

v1[stoi(deadend)] = v2[stoi(deadend)] = -1;

if (v1[start] == -1) return -1;

if (start == goal) return 0;

v1[start] = 1;

v2[goal] = 1;

int s1 = 0;

int s2 = 0;

q1.push(start);

q2.push(goal);

while (!q1.empty() && !q2.empty()) {

if (!q1.empty()) ++s1;

const int size = q1.size();

for (int i = 0; i < size; ++i) {

const int curr = q1.front();

q1.pop();

for (int i = 0; i < 4; ++i) {

int r = (curr / bases[i]) % 10;

for (int j = -1; j <= 1; j += 2) {

const int next = curr + ((r + j + 10) % 10 - r) * bases[i];

if (v2[next] == 1) return s1 + s2;

if (v1[next]) continue;

q1.push(next);

v1[next] = 1;

}

swap(q1, q2);

swap(v1, v2);

swap(s1, s2);

}

return -1;

}

};

Java

// Author: Huahua

// Runtime: 132 ms

class Solution {

public int openLock(String[] deadends, String target) {

String start = "0000";

Set<String> dead = new HashSet();

for (String d: deadends) dead.add(d);

if (dead.contains(start)) return -1;

Queue<String> queue = new LinkedList();

queue.offer(start);

Set<String> visited = new HashSet();

visited.add(start);

int steps = 0;

while (!queue.isEmpty()) {

++steps;

int size = queue.size();

for (int s = 0; s < size; ++s) {

String node = queue.poll();

for (int i = 0; i < 4; ++i) {

for (int j = -1; j <= 1; j += 2) {

char[] chars = node.toCharArray();

chars[i] = (char)(((chars[i] - '0') + j + 10) % 10 + '0');

String next = new String(chars);

if (next.equals(target)) return steps;

if (dead.contains(next) || visited.contains(next))

continue;

visited.add(next);

queue.offer(next);

}

return -1;

}

Python

"""

Author: Huahua

Runtime: 955 ms

"""

class Solution:

def openLock(self, deadends, target):

from collections import deque

deads = set(deadends)

start = '0000'

if start in deads: return -1

q = deque([(start, 0)])

visited = set(start)

while q:

node, step = q.popleft()

for i in range(0, 4):

for j in [-1, 1]:

nxt = node[:i] + str((int(node[i]) + j + 10) % 10) + node[i+1:]

if nxt == target: return step + 1

if nxt in deads or nxt in visited: continue

q.append((nxt, step + 1))

visited.add(nxt)

return -1

Python / Int state

"""

Author: Huahua

Runtime: 568 ms

"""

class Solution:

def openLock(self, deadends, target):

from collections import deque

bases = [1, 10, 100, 1000]

deads = set(int(x) for x in deadends)

start, goal = int('0000'), int(target)

if start in deads: return -1

if start == goal: return 0

q = deque([(start, 0)])

visited = set([start])

while q:

node, step = q.popleft()

for i in range(0, 4):

r = (node // bases[i]) % 10

for j in [-1, 1]:

nxt = node + ((r + j + 10) % 10 - r) * bases[i]

if nxt == goal: return step + 1

if nxt in deads or nxt in visited: continue

q.append((nxt, step + 1))

visited.add(nxt)

return -1

花花酱 LeetCode 126. Word Ladder II

By zxi on September 26, 2017

Problem:

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 transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

[

["hit","hot","dot","dog","cog"],

["hit","hot","lot","log","cog"]

]

Note:

Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS to construct the graph + DFS to extract the paths

Solutions:

C++, BFS 1

// Author: Huahua

// Running Time: 216 ms (better than 65.42%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return {};

dict.erase(beginWord);

dict.erase(endWord);

unordered_map<string, int> steps{{beginWord, 1}};

unordered_map<string, vector<string>> parents;

queue<string> q;

q.push(beginWord);

vector<vector<string>> ans;

const int l = beginWord.length();

int step = 0;

bool found = false;

while (!q.empty() && !found) {

++step;

for (int size = q.size(); size > 0; size--) {

const string p = q.front(); q.pop();

string w = p;

for (int i = 0; i < l; i++) {

const char ch = w[i];

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

if (j == ch) continue;

w[i] = j;

if (w == endWord) {

parents[w].push_back(p);

found = true;

} else {

// Not a new word, but another transform

// with the same number of steps

if (steps.count(w) && step < steps.at(w))

parents[w].push_back(p);

}

if (!dict.count(w)) continue;

dict.erase(w);

q.push(w);

steps[w] = steps.at(p) + 1;

parents[w].push_back(p);

}

w[i] = ch;

}

if (found) {

vector<string> curr{endWord};

getPaths(endWord, beginWord, parents, curr, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& beginWord,

const unordered_map<string, vector<string>>& parents,

vector<string>& curr,

vector<vector<string>>& ans) {

if (word == beginWord) {

ans.push_back(vector<string>(curr.rbegin(), curr.rend()));

return;

}

for (const string& p : parents.at(word)) {

curr.push_back(p);

getPaths(p, beginWord, parents, curr, ans);

curr.pop_back();

}

};

C++ / BFS 2

// Author: Huahua

// Running time: 129 ms (better than 80.67%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

vector<vector<string>> ans;

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return ans;

dict.erase(endWord);

const int l = beginWord.length();

unordered_set<string> q{beginWord}, p;

unordered_map<string, vector<string>> children;

bool found = false;

while (!q.empty() && !found) {

for (const string& word : q)

dict.erase(word);

for (const string& word : q) {

string curr = word;

for (int i = 0; i < l; i++) {

char ch = curr[i];

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

curr[i] = j;

if (curr == endWord) {

found = true;

children[word].push_back(curr);

} else if (dict.count(curr) && !found) {

p.insert(curr);

children[word].push_back(curr);

}

curr[i] = ch;

}

std::swap(p, q);

p.clear();

}

if (found) {

vector<string> path{beginWord};

getPaths(beginWord, endWord, children, path, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& endWord,

const unordered_map<string, vector<string>>& children,

vector<string>& path,

vector<vector<string>>& ans) {

if (word == endWord) {

ans.push_back(path);

return;

}

const auto it = children.find(word);

if (it == children.cend()) return;

for (const string& child : it->second) {

path.push_back(child);

getPaths(child, endWord, children, path, ans);

path.pop_back();

}

};

C++ / Bidirectional BFS

// Author: Huahua

// Running time: 39 ms (better than 93.74%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

vector<vector<string>> ans;

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return ans;

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

unordered_map<string, vector<string>> children;

bool found = false;

bool backward = false;

while (!q1.empty() && !q2.empty() && !found) {

// Always expend the smaller queue first

if (q1.size() > q2.size()) {

std::swap(q1, q2);

backward = !backward;

}

for (const string& w : q1)

dict.erase(w);

for (const string& w : q2)

dict.erase(w);

unordered_set<string> q;

for (const string& word : q1) {

string curr = word;

for (int i = 0; i < l; i++) {

char ch = curr[i];

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

curr[i] = j;

const string* parent = &word;

const string* child = &curr;

if (backward)

std::swap(parent, child);

if (q2.count(curr)) {

found = true;

children[*parent].push_back(*child);

} else if (dict.count(curr) && !found) {

q.insert(curr);

children[*parent].push_back(*child);

}

curr[i] = ch;

}

std::swap(q, q1);

}

if (found) {

vector<string> path{beginWord};

getPaths(beginWord, endWord, children, path, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& endWord,

const unordered_map<string, vector<string>>& children,

vector<string>& path,

vector<vector<string>>& ans) {

if (word == endWord) {

ans.push_back(path);

return;

}

const auto it = children.find(word);

if (it == children.cend()) return;

for (const string& child : it->second) {

path.push_back(child);

getPaths(child, endWord, children, path, ans);

path.pop_back();

}

};