Posts tagged as “hard”

花花酱 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 218. The Skyline Problem

By zxi on September 22, 2017

Problem:

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

The number of buildings in any input list is guaranteed to be in the range [0, 10000].
The input list is already sorted in ascending order by the left x position Li.
The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Idea:

Sweep line

Time Complexity:

O(nlogn)

Space Complexity:

O(n)

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 664. Strange Printer

By zxi on September 20, 2017

Problem:

There is a strange printer with the following two special requirements:

The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Input: "aaabbb"

Output: 2

Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: "aba"

Output: 2

Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Hint: Length of the given string will not exceed 100.

Idea:

Dynamic programming

Time Complexity:

O(n^3)

Space Complexity:

O(n^2)

Solution:

C++

// Author: Huahua

// Time Complexity: O(n^3)

// Space Complexity: O(n^2)

// Running Time: 22 ms

class Solution {

public:

int strangePrinter(const string& s) {

int l = s.length();

t_ = vector<vector<int>>(l, vector<int>(l, 0));

return turn(s, 0, s.length() - 1);

}

private:

// Minimal turns to print s[i] to s[j]

int turn(const string& s, int i, int j) {

// Empty string

if (i > j) return 0;

// Solved

if (t_[i][j] > 0) return t_[i][j];

// Default behavior, print s[i] to s[j-1] and print s[j]

int ans = turn(s, i, j-1) + 1;

for (int k = i; k < j; ++k)

if (s[k] == s[j])

ans = min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));

return t_[i][j] = ans;

}

vector<vector<int>> t_;

};

Java

// Author: Huahua

// Time Complexity: O(n^3)

// Space Complexity: O(n^2)

// Running Time: 31 ms (beat 99.25%) 9/2017

class Solution {

public int strangePrinter(String s) {

int l = s.length();

t_ = new int[l][l];

return turn(s.toCharArray(), 0, l - 1);

}

// Minimal turns to print s[i] to s[j]

private int turn(char[] s, int i, int j) {

// Empty string

if (i > j) return 0;

// Solved

if (t_[i][j] > 0) return t_[i][j];

// Default behavior, print s[i] to s[j-1] and print s[j]

int ans = turn(s, i, j-1) + 1;

for (int k = i; k < j; ++k)

if (s[k] == s[j])

ans = Math.min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));

return t_[i][j] = ans;

}

private int[][] t_;

}

Python3

"""

Author: Huahua

Time Complexity: O(n^3)

Space Complexity: O(n^2)

Running Time: 895 ms (beat 66%) 9/2017

"""

class Solution(object):

def strangePrinter(self, s):

"""

:type s: str

:rtype: int

"""

l = len(s)

self._t = [[0 for _ in xrange(l)] for _ in xrange(l)]

return self._turns(s, 0, l - 1)

def _turns(self, s, i, j):

if i > j: return 0

if self._t[i][j] > 0: return self._t[i][j]

ans = self._turns(s, i, j - 1) + 1

for k in xrange(i, j):

if s[k] == s[j]:

ans = min(ans, self._turns(s, i, k)

+ self._turns(s, k + 1, j-1))

self._t[i][j] = ans

return self._t[i][j]

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

By zxi on September 17, 2017

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

/ \

2 3

/ \

4 5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Idea:

Recursion

Time Complexity O(n)

Solution 1: ASCII

C++

// Author: Huahua

// Running time: 39 ms

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

void serialize(TreeNode* root, ostringstream& out) {

if (!root) {

out << "# ";

return;

}

out << root->val << " ";

serialize(root->left, out);

serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

string val;

in >> val;

if (val == "#") return nullptr;

TreeNode* root = new TreeNode(stoi(val));

root->left = deserialize(in);

root->right = deserialize(in);

return root;

}

};

Solution 2: Binary

C++

// Author: Huahua

// Running time: 23 ms (beat 98.07%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, ostringstream& out) {

char status = 0;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

out.write(&status, sizeof(char));

if (!root) return;

out.write(reinterpret_cast<char*>(&(root->val)), sizeof(root->val));

if (root->left) serialize(root->left, out);

if (root->right) serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

char status;

in.read(&status, sizeof(char));

if (!status & ROOT) return nullptr;

auto root = new TreeNode(0);

in.read(reinterpret_cast<char*>(&root->val), sizeof(root->val));

root->left = (status & LEFT) ? deserialize(in) : nullptr;

root->right = (status & RIGHT) ? deserialize(in) : nullptr;

return root;

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

C++ (string)

// Author: Huahua

// Running time: 23 ms (<98.13%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

string s;

serialize(root, s);

return s;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

int pos = 0;

return deserialize(data, pos);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, string& s) {

char status = ROOT_NULL;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

s.push_back(status);

if (!root) return;

s.append(reinterpret_cast<char*>(&root->val), sizeof(root->val));

if (root->left) serialize(root->left, s);

if (root->right) serialize(root->right, s);

}

TreeNode* deserialize(const string& s, int& pos) {

char status = s[pos++];

if (!status) return nullptr;

TreeNode* root = new TreeNode(0);

memcpy(&root->val, s.data() + pos, sizeof(root->val));

pos += sizeof(root->val);

root->left = (status & LEFT) ? deserialize(s, pos) : nullptr;

root->right = (status & RIGHT) ? deserialize(s, pos) : nullptr;

return root;

}

};

Posts tagged as “hard”

花花酱 LeetCode 126. Word Ladder II

花花酱 LeetCode 218. The Skyline Problem

Solution1: Heap

C++

Java

Solution 2: Multiset

C++

花花酱 LeetCode 664. Strange Printer

C++

Java

Python3

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed