花花酱 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();

}

};

花花酱 LeetCode 127. Word Ladder

By zxi on September 25, 2017

https://leetcode.com/problems/word-ladder/description/

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. Note that beginWord is not a transformed word.

For example,

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

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.
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

Time Complexity: O(n*26^l) -> O(n*26^l/2), l = len(word), n=|wordList|

Space Complexity: O(n)

Solution 1: BFS

C++

// Author: Huahua

// Running time: 93 ms

class Solution {

public:

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

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

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

queue<string> q;

q.push(beginWord);

int l = beginWord.length();

int step = 0;

while (!q.empty()) {

++step;

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

string w = q.front();

q.pop();

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

char ch = w[i];

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

w[i] = j;

// Found the solution

if (w == endWord) return step + 1;

// Not in dict, skip it

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

// Remove new word from dict

dict.erase(w);

// Add new word into queue

q.push(w);

}

w[i] = ch;

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 92 ms (<76.61%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Queue<String> q = new ArrayDeque<>();

q.offer(beginWord);

int l = beginWord.length();

int steps = 0;

while (!q.isEmpty()) {

++steps;

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

String w = q.poll();

char[] chs = w.toCharArray();

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

char ch = chs[i];

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

if (c == ch) continue;

chs[i] = c;

String t = new String(chs);

if (t.equals(endWord)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.offer(t);

}

chs[i] = ch;

}

return 0;

}

Solution 2: Bidirectional BFS

C++

// Author: Huahua

// Running time: 32 ms (better than 96.6%)

class Solution {

public:

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

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

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

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

int step = 0;

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

++step;

// Always expend the smaller queue first

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

std::swap(q1, q2);

unordered_set<string> q;

for (string w : q1) {

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

char ch = w[i];

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

w[i] = j;

if (q2.count(w)) return step + 1;

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

dict.erase(w);

q.insert(w);

}

w[i] = ch;

}

std::swap(q, q1);

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 31 ms (<95.17%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Set<String> q1 = new HashSet<>();

Set<String> q2 = new HashSet<>();

q1.add(beginWord);

q2.add(endWord);

int l = beginWord.length();

int steps = 0;

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

++steps;

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

Set<String> tmp = q1;

q1 = q2;

q2 = tmp;

}

Set<String> q = new HashSet<>();

for (String w : q1) {

char[] chs = w.toCharArray();

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

char ch = chs[i];

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

chs[i] = c;

String t = new String(chs);

if (q2.contains(t)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.add(t);

}

chs[i] = ch;

}

q1 = q;

}

return 0;

}

Python

"""

Author: Huahua

Running time: 115 ms (better than 96.84%)

"""

class Solution(object):

def ladderLength(self, beginWord, endWord, wordList):

wordDict = set(wordList)

if endWord not in wordDict: return 0

l = len(beginWord)

s1 = {beginWord}

s2 = {endWord}

wordDict.remove(endWord)

step = 0

while len(s1) > 0 and len(s2) > 0:

step += 1

if len(s1) > len(s2): s1, s2 = s2, s1

s = set()

for w in s1:

new_words = [

w[:i] + t + w[i+1:] for t in string.ascii_lowercase for i in xrange(l)]

for new_word in new_words:

if new_word in s2: return step + 1

if new_word not in wordDict: continue

wordDict.remove(new_word)

s.add(new_word)

s1 = s

return 0

Problem:

https://leetcode.com/problems/next-closest-time/description/
no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, 
which occurs 5 minutes later.  
It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. 
It may be assumed that the returned time is next day's time since it is smaller 
than the input time numerically.

Ads

Solution1: Brute force

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

set<char> s(time.begin(), time.end());

int hour = stoi(time.substr(0, 2));

int min = stoi(time.substr(3, 2));

while (true) {

if (++min == 60) {

min = 0;

(++hour) %= 24;

}

char buffer[5];

sprintf(buffer, "%02d:%02d", hour, min);

set<char> s2(buffer, buffer + sizeof(buffer));

if (includes(s.begin(), s.end(), s2.begin(), s2.end()))

return string(buffer);

}

return time;

}

};

Java

// Author: Huahua

// Running time: 85 ms

class Solution {

public String nextClosestTime(String time) {

int hour = Integer.parseInt(time.substring(0, 2));

int min = Integer.parseInt(time.substring(3, 5));

while (true) {

if (++min == 60) {

min = 0;

++hour;

hour %= 24;

}

String curr = String.format("%02d:%02d", hour, min);

Boolean valid = true;

for (int i = 0; i < curr.length(); ++i)

if (time.indexOf(curr.charAt(i)) < 0) {

valid = false;

break;

}

if (valid) return curr;

}

Python

"""

Author: Huahua

Running time: 65 ms

"""

class Solution:

def nextClosestTime(self, time):

s = set(time)

hour = int(time[0:2])

minute = int(time[3:5])

while True:

minute += 1

if minute == 60:

minute = 0

hour = 0 if hour == 23 else hour + 1

time = "%02d:%02d" % (hour, minute)

if set(time) <= s:

return time

Solution 2: DFS

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

vector<int> d = {

time[0] - '0', time[1] - '0', time[3] - '0', time[4] - '0' };

int h = d[0] * 10 + d[1];

int m = d[2] * 10 + d[3];

vector<int> curr(4, 0);

int now = toTime(h, m);

int best = now;

dfs(0, d, curr, now, best);

char buff[5];

sprintf(buff, "%02d:%02d", best / 60, best % 60);

return string(buff);

}

private:

void dfs(int dep, const vector<int>& digits, vector<int>& curr, int time, int& best) {

if (dep == 4) {

int curr_h = curr[0] * 10 + curr[1];

int curr_m = curr[2] * 10 + curr[3];

if (curr_h > 23 || curr_m > 59) return;

int curr_time = toTime(curr_h, curr_m);

if (timeDiff(time, curr_time) < timeDiff(time, best))

best = curr_time;

return;

}

for (int digit : digits) {

curr[dep] = digit;

dfs(dep + 1, digits, curr, time, best);

}

int toTime(int h, int m) {

return h * 60 + m;

}

int timeDiff(int t1, int t2) {

if (t1 == t2) return INT_MAX;

return ((t2 - t1) + 24 * 60) % (24 * 60);

}

};

Solution 3: Brute force + Time library

Python3

"""

Author: Huahua

Running time: 292 ms

"""

from datetime import *

class Solution:

def nextClosestTime(self, time):

s = set(time)

while True:

time = (datetime.strptime(time, '%H:%M') +

timedelta(minutes=1)).strftime('%H:%M')

if set(time) <= s:

return time

Solution1: Heap

C++

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

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

// events, x, h, id, type (1=entering, -1=leaving)

vector<Event> events;

int id = 0;

for (const auto& b : buildings) {

events.push_back(Event{id, b[0], b[2], 1});

events.push_back(Event{id, b[1], b[2], -1});

++id;

}

// Sort events by x

sort(events.begin(), events.end());

// Init the heap

MaxHeap heap(buildings.size());

vector<pair<int, int>> ans;

// Process all the events

for (const auto& event: events) {

int x = event.x;

int h = event.h;

int id = event.id;

int type = event.type;

if (type == 1) {

if (h > heap.Max())

ans.emplace_back(x, h);

heap.Add(h, id);

} else {

heap.Remove(id);

if (h > heap.Max())

ans.emplace_back(x, heap.Max());

}

return ans;

}

private:

struct Event {

int id;

int x;

int h;

int type;

// sort by x+, type-, h,

bool operator<(const Event& e) const {

if (x == e.x)

// Entering event h from large to small

// Leaving event h from small to large

return type * h > e.type * e.h;

return x < e.x;

}

};

class MaxHeap {

public:

MaxHeap(int max_items):

idx_(max_items, -1), vals_(max_items), size_(0) {}

// Add an item into the heap. O(log(n))

void Add(int key, int id) {

idx_[id] = size_;

vals_[size_] = {key, id};

++size_;

HeapifyUp(idx_[id]);

}

// Remove an item. O(log(n))

void Remove(int id) {

int idx_to_evict = idx_[id];

// swap with the last element

SwapNode(idx_to_evict, size_ - 1);

--size_;

HeapifyDown(idx_to_evict);

}

bool Empty() const {

return size_ == 0;

}

// Return the max of heap

int Max() const {

return Empty() ? 0 : vals_.front().first;

}

private:

void SwapNode(int i, int j) {

if (i == j) return;

std::swap(idx_[vals_[i].second], idx_[vals_[j].second]);

std::swap(vals_[i], vals_[j]);

}

void HeapifyUp(int i) {

while (i != 0) {

int p = (i - 1) / 2;

if (vals_[i].first <= vals_[p].first)

return;

SwapNode(i, p);

i = p;

}

// Make the heap valid again. O(log(n))

void HeapifyDown(int i) {

while (true) {

int c1 = i*2 + 1;

int c2 = i*2 + 2;

// No child

if (c1 >= size_) return;

// Get the index of the max child

int c = (c2 < size_

&& vals_[c2].first > vals_[c1].first ) ? c2 : c1;

// If key[c] is greater than key[i], swap them and

// continue to HeapifyDown(c)

if (vals_[c].first <= vals_[i].first)

return;

SwapNode(c, i);

i = c;

}

// {key, id}

vector<pair<int,int>> vals_;

// Index of the i-th item in vals_

vector<int> idx_;

int size_;

};

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

// Author: Huahua

// Running time: 91 ms (beats 79.1%)

class Solution {

private MaxHeap heap;

public List<int[]> getSkyline(int[][] buildings) {

int n = buildings.length;

// {x, h, id}

ArrayList<int[]> es = new ArrayList<int[]>();

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

es.add(new int[]{ buildings[i][0], buildings[i][2], i});

es.add(new int[]{ buildings[i][1], -buildings[i][2], i});

}

es.sort((e1, e2) -> {

return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0]; });

List<int[]> ans = new ArrayList<int[]>();

heap = new MaxHeap(n);

for (int[] e : es) {

int x = e[0];

int h = e[1];

int id = e[2];

Boolean entering = h > 0;

h = Math.abs(h);

if (entering) {

if (h > heap.max())

ans.add(new int[]{x, h});

heap.add(h, id);

} else {

heap.remove(id);

if (h > heap.max())

ans.add(new int[]{x, heap.max()});

}

return ans;

}

private class MaxHeap {

// (key, id)

private List<int[]> nodes;

// idx[i] = index of building[i] in nodes

private int[] idx;

public MaxHeap(int size) {

idx = new int[size];

nodes = new ArrayList<int[]>();

}

public void add(int key, int id) {

idx[id] = nodes.size();

nodes.add(new int[]{key, id});

heapifyUp(idx[id]);

}

public void remove(int id) {

int idx_to_evict = idx[id];

swapNode(idx_to_evict, nodes.size() - 1);

idx[id] = -1;

nodes.remove(nodes.size() - 1);

heapifyUp(idx_to_evict);

heapifyDown(idx_to_evict);

}

public Boolean empty() {

return nodes.isEmpty();

}

public int max() {

return empty() ? 0 : nodes.get(0)[0];

}

private void heapifyUp(int i) {

while (i != 0) {

int p = (i - 1) / 2;

if (nodes.get(i)[0] <= nodes.get(p)[0])

return;

swapNode(i, p);

i = p;

}

private void swapNode(int i, int j) {

int tmpIdx = idx[nodes.get(i)[1]];

idx[nodes.get(i)[1]] = idx[nodes.get(j)[1]];

idx[nodes.get(j)[1]] = tmpIdx;

int[] tmpNode = nodes.get(i);

nodes.set(i, nodes.get(j));

nodes.set(j, tmpNode);

}

private void heapifyDown(int i) {

while (true) {

int c1 = i*2 + 1;

int c2 = i*2 + 2;

if (c1 >= nodes.size()) return;

int c = (c2 < nodes.size()

&& nodes.get(c2)[0] > nodes.get(c1)[0]) ? c2 : c1;

if (nodes.get(c)[0] <= nodes.get(i)[0])

return;

swapNode(c, i);

i = c;

}

Solution 2: Multiset

C++

// Author: Huahua

// Time Complexity: O(nlogn)

// Space Complexity: O(n)

// Running Time: 22 ms

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

typedef pair<int, int> Event;

// events, x, h

vector<Event> es;

hs_.clear();

for (const auto& b : buildings) {

es.emplace_back(b[0], b[2]);

es.emplace_back(b[1], -b[2]);

}

// Sort events by x

sort(es.begin(), es.end(), [](const Event& e1, const Event& e2){

if (e1.first == e2.first) return e1.second > e2.second;

return e1.first < e2.first;

});

vector<pair<int, int>> ans;

// Process all the events

for (const auto& e: es) {

int x = e.first;

bool entering = e.second > 0;

int h = abs(e.second);

if (entering) {

if (h > this->maxHeight())

ans.emplace_back(x, h);

hs_.insert(h);

} else {

hs_.erase(hs_.equal_range(h).first);

if (h > this->maxHeight())

ans.emplace_back(x, this->maxHeight());

}

return ans;

}

private:

int maxHeight() const {

if (hs_.empty()) return 0;

return *hs_.rbegin();

}

multiset<int> hs_;

};

花花酱 LeetCode 126. Word Ladder II

花花酱 LeetCode 127. Word Ladder

Solution 1: BFS

C++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems

花花酱 LeetCode 681. Next Closest Time

Problem:

Example 1:

Example 2:

Solution1: Brute force

C++

Java

Python

Solution 2: DFS

C++

Solution 3: Brute force + Time library

Python3

Related Problems:

花花酱 LeetCode 682. Baseball Game

花花酱 LeetCode 218. The Skyline Problem

Solution1: Heap

C++

Java

Solution 2: Multiset

C++

Huahua's Tech Road

花花酱 LeetCode 126. Word Ladder II

花花酱 LeetCode 127. Word Ladder

Solution 1: BFS

C++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems

花花酱 LeetCode 681. Next Closest Time

Problem:

Example 1:

Example 2:

Solution1: Brute force

C++

Java

Python

Solution 2: DFS

C++

Solution 3: Brute force + Time library

Python3

Related Problems:

花花酱 LeetCode 682. Baseball Game

花花酱 LeetCode 218. The Skyline Problem

Solution1: Heap

C++

Java

Solution 2: Multiset

C++