Posts tagged as “BFS”

花花酱 LeetCode 17. Letter Combinations of a Phone Number

By zxi on December 29, 2017

题目大意：给你一串电话号码，输出可以由这串电话号码打出的所有字符串。

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1 2	Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> letterCombinations(string digits) {

if (digits.empty()) return {};

vector<vector<char>> d(10);

d[0] = {' '};

d[1] = {};

d[2] = {'a','b','c'};

d[3] = {'d','e','f'};

d[4] = {'g','h','i'};

d[5] = {'j','k','l'};

d[6] = {'m','n','o'};

d[7] = {'p','q','r','s'};

d[8] = {'t','u','v'};

d[9] = {'w','x','y','z'};

string cur;

vector<string> ans;

dfs(digits, d, 0, cur, ans);

return ans;

}

private:

void dfs(const string& digits,

const vector<vector<char>>& d,

int l, string& cur, vector<string>& ans) {

if (l == digits.length()) {

ans.push_back(cur);

return;

}

for (const char c : d[digits[l] - '0']) {

cur.push_back(c);

dfs(digits, d, l + 1, cur, ans);

cur.pop_back();

}

};

Java

// Author: Huahua

// Running time: 3 ms

class Solution {

public List<String> letterCombinations(String digits) {

String[] d = new String[]{" ",

"",

"abc",

"def",

"ghi",

"jkl",

"mno",

"pqrs",

"tuv",

"wxyz"};

char[] cur = new char[digits.length()];

List<String> ans = new ArrayList<>();

dfs(digits, d, 0, cur, ans);

return ans;

}

private void dfs(String digits, String[] d,

int l, char[] cur, List<String> ans) {

if (l == digits.length()) {

if (l > 0) ans.add(new String(cur));

return;

}

String s = d[Character.getNumericValue(digits.charAt(l))];

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

cur[l] = s.charAt(i);

dfs(digits, d, l + 1, cur, ans);

}

Python3

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def letterCombinations(self, digits):

def dfs(digits, d, l, cur, ans):

if l == len(digits):

if l > 0: ans.append("".join(cur))

return

for c in d[ord(digits[l]) - ord('0')]:

cur[l] = c

dfs(digits, d, l + 1, cur, ans)

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]

cur = [' ' for _ in range(len(digits))]

ans = []

dfs(digits, d, 0, cur, ans)

return ans

Solution 2: BFS

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<string> letterCombinations(string digits) {

if (digits.empty()) return {};

vector<vector<char>> d(10);

d[0] = {' '};

d[1] = {};

d[2] = {'a','b','c'};

d[3] = {'d','e','f'};

d[4] = {'g','h','i'};

d[5] = {'j','k','l'};

d[6] = {'m','n','o'};

d[7] = {'p','q','r','s'};

d[8] = {'t','u','v'};

d[9] = {'w','x','y','z'};

vector<string> ans{""};

for (char digit : digits) {

vector<string> tmp;

for (const string& s : ans)

for (char c : d[digit - '0'])

tmp.push_back(s + c);

ans.swap(tmp);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 4 ms

class Solution {

public List<String> letterCombinations(String digits) {

if (digits.length() == 0) return new ArrayList<String>();

String[] d = new String[]{" ",

"",

"abc",

"def",

"ghi",

"jkl",

"mno",

"pqrs",

"tuv",

"wxyz"};

List<String> ans = new ArrayList<>();

ans.add("");

for (char digit : digits.toCharArray()) {

List<String> tmp = new ArrayList<>();

for (String t : ans) {

String s = d[Character.getNumericValue(digit)];

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

tmp.add(t + s.charAt(i));

}

ans = tmp;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 61 ms

"""

class Solution:

def letterCombinations(self, digits):

if not digits: return []

d = [" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv","wxyz"]

ans = [""]

for digit in digits:

tmp = []

for s in ans:

for c in d[ord(digit) - ord('0')]:

tmp.append(s + c)

ans = tmp

return ans

花花酱 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 742. Closest Leaf in a Binary Tree

By zxi on December 12, 2017

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the value of the closest leaf node to target k in the tree.

Here, closest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:

root = [1, 3, 2], k = 1

Diagram of binary tree:

/ \

3 2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the closest leaf node to the target of 1.

Example 2:

Input:

root = [1], k = 1

Output: 1

Explanation: The closest leaf node is the root node itself.

Example 3:

Input:

root = [1,2,3,4,null,null,null,5,null,6], k = 2

Diagram of binary tree:

/ \

2 3

Output: 3

Explanation: The leaf node with value 3 (and not the leaf node with value 6) is closest to the node with value 2.

Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.

题目大意:

给你一棵树，每个节点的值都不相同。

给定一个节点值，让你找到离这个节点距离最近的叶子节点的值。

Idea:

Shortest path from source to any leaf nodes in a undirected unweighted graph.

问题转换为在无向/等权重的图中找一条从起始节点到任意叶子节点最短路径。

Solution:

C++ / DFS + BFS

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

int findClosestLeaf(TreeNode* root, int k) {

graph_.clear();

start_ = nullptr;

buildGraph(root, nullptr, k);

queue<TreeNode*> q;

q.push(start_);

unordered_set<TreeNode*> seen;

while (!q.empty()) {

int size = q.size();

while (size-->0) {

TreeNode* curr = q.front();

q.pop();

seen.insert(curr);

if (!curr->left && !curr->right) return curr->val;

for (TreeNode* node : graph_[curr])

if (!seen.count(node)) q.push(node);

}

return 0;

}

private:

void buildGraph(TreeNode* node, TreeNode* parent, int k) {

if (!node) return;

if (node->val == k) start_ = node;

if (parent) {

graph_[node].push_back(parent);

graph_[parent].push_back(node);

}

buildGraph(node->left, node, k);

buildGraph(node->right, node, k);

}

unordered_map<TreeNode*, vector<TreeNode*>> graph_;

TreeNode* start_;

};

花花酱 LeetCode 690. Employee Importance

By zxi on September 28, 2017

https://leetcode.com/problems/employee-importance/description/

Problem:

ou are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1

Output: 11

Explanation:

Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3.

So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:

One employee has at most one direct leader and may have several subordinates.
The maximum number of employees won’t exceed 2000.

Idea:

BFS / DFS

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++ / BFS

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

int getImportance(vector<Employee*> employees, int id) {

unordered_map<int, Employee*> es;

for (auto e : employees)

es.emplace(e->id, e);

queue<int> q;

q.push(id);

int sum = 0;

while (!q.empty()) {

int eid = q.front(); q.pop();

auto e = es[eid];

sum += e->importance;

for (auto rid : e->subordinates)

q.push(rid);

}

return sum;

}

};

C++ / DFS

class Solution {

public:

int getImportance(vector<Employee*> employees, int id) {

unordered_map<int, Employee*> es;

for (auto e : employees)

es.emplace(e->id, e);

return dfs(id, es);

}

private:

int dfs(int id, const unordered_map<int, Employee*>& es) {

const auto e = es.at(id);

int sum = e->importance;

for (int rid : e->subordinates)

sum += dfs(rid, es);

return sum;

}

};

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

}

};