Graph: Breadth First Search
126. Word Ladder II
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 intermediate word must exist in the word list For example,
Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]Note: All words have the same length. All words contain only lowercase alphabetic characters.
class Solution {
public:
vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
unordered_map<string, unordered_set<string>> traces;
unordered_set<string> set1 {start};
unordered_set<string> set2 {end};
bfs_traces(set1, set2, dict, traces, false);
vector<string> slu{start};
vector<vector<string>> res;
get_paths(traces, slu, res, start, end);
return res;
}
void bfs_traces(unordered_set<string> set1, unordered_set<string> set2, unordered_set<string> &dict,
unordered_map<string, unordered_set<string>>& traces, bool reversed) {
if (set1.size() > set2.size()) return bfs_traces(set2, set1, dict, traces, !reversed);
if (set1.size() == 0) return;
for (auto word : set1) dict.erase(word);
bool done = false;
unordered_set<string> nextLevel;
for (auto str : set1) {
for (size_t i = 0; i < str.length(); ++i) {
string next = str;
for (char c = 'a'; c <= 'z'; ++c) {
next[i] = c;
if (str[i] == c || dict.find(next) == dict.end()) continue;
string key = reversed ? next : str;
string val = reversed ? str : next;
traces[key].insert(val);
if (set2.find(next) != set2.end()) {
done = true;
}
if (!done) nextLevel.insert(next);
}
}
}
if (!done) return bfs_traces(set2, nextLevel, dict, traces, !reversed);
}
void get_paths(unordered_map<string, unordered_set<string>>& traces, vector<string>& slu,
vector<vector<string>>& res, string start, string end) {
if (start == end) {
res.push_back(slu);
return;
}
for (auto word : traces[start]) {
slu.push_back(word);
get_paths(traces, slu, res, word, end);
slu.pop_back();
}
}
};
130. Surrounded Regions
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X X O O X X X O X X O X XAfter running your function, the board should be:
X X X X X X X X X X X X X O X XShow Tags Show Similar Problems
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (!board.size() || !board[0].size()) return;
int m = board.size();
int n = board[0].size();
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
if (board[i][0] == 'O') {
visited[i][0] = true;
q.push({i, 0});
}
if (n > 1 && board[i][n-1] == 'O') {
visited[i][n-1] = true;
q.push({i, n-1});
}
}
for (int j = 0; j < n; ++j) {
if (board[0][j] == 'O' && !visited[0][j]) {
visited[0][j] = true;
q.push({0,j});
}
if (m > 1 && board[m-1][j] == 'O' && !visited[m-1][j]) {
visited[m-1][j] = true;
q.push({m-1, j});
}
}
vector<int> steps{0, 1, 0, -1, 0};
while (!q.empty()) {
auto cur = q.front(); q.pop();
for (int i = 0; i < steps.size() - 1; ++i) {
int x = cur.first + steps[i];
int y = cur.second + steps[i+1];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !visited[x][y]) {
q.push({x, y});
visited[x][y] = true;
}
}
}
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (board[i][j] == 'O' && !visited[i][j]) board[i][j] = 'X';
}
}
}
};
97. Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example, Given: s1 = "aabcc", s2 = "dbbca",
When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.
BFS 和 DFS 的解法都是4ms, DP的解法是12ms
class Solution { // DP
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3) return false;
vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));
for (size_t i = 0; i <= len1; ++i) {
for (size_t j = 0; j <= len2; ++j) {
if (i == 0 && j == 0) dp[i][j] = true;
else if (i == 0) {
dp[i][j] = dp[i][j-1] && (s3[i+j-1] == s2[j-1]);
} else if (j == 0) {
dp[i][j] = dp[i-1][j] && (s3[i+j-1] == s1[i-1]);
} else {
dp[i][j] = (dp[i][j-1] && (s3[i+j-1] == s2[j-1])) || (dp[i-1][j] && (s3[i+j-1] == s1[i-1])) ;
}
}
}
return dp[len1][len2];
}
};
class Solution { // dfs
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3) return false;
vector<vector<bool>> isInvalid(len1 + 1, vector<bool>(len2 + 1, false));
return dfs(s1, s2, s3, 0, 0, 0, isInvalid);
}
bool dfs(const string& s1, const string& s2, const string& s3, int i, int j, int k, vector<vector<bool>>& isInvalid) {
if (isInvalid[i][j]) return false;
if (k == s3.size()) return true;
bool valid = (i < s1.size() && s1[i] == s3[k] && dfs(s1, s2, s3, i+1, j, k+1, isInvalid)) ||
(j < s2.size() && s2[j] == s3[k] && dfs(s1, s2, s3, i, j+1, k+1, isInvalid));
isInvalid[i][j] = !valid;
return valid;
}
};
class Solution { // bfs
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3) return false;
// unordered_set<int> visited;
vector<vector<bool>> visited(len1 + 1, vector<bool>(len2 + 1, false));
queue<pair<int, int>> q;
q.push({-1, -1});
while (!q.empty()) {
auto cur = q.front(); q.pop();
int i = cur.first + 1;
int j = cur.second + 1;
if (i == len1 && j == len2) return true;
if (i + j < len3) {
char next = s3[i+j];
if (i < len1 && s1[i] == next) {
if (!visited[i+1][j]) {
q.push({i, j-1});
visited[i+1][j] = true;
}
}
if (j < len2 && s2[j] == next) {
if (!visited[i][j+1]) {
q.push({i-1, j});
visited[i][j+1] = true;
}
}
}
}
return false;
}
};
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
class Solution {
public:
int numSquares(int n) {
if (n <= 1) return n;
vector<int> squares;
vector<int> cnt(n+1);
queue<int> q;
for (int i = 1; i*i <= n; ++i) {
squares.push_back(i*i);
cnt[i*i] = 1;
q.push(i*i);
}
if (squares.back() == n) return 1;
int num = 1;
while (!q.empty()) {
num++;
int len = q.size();
while (len--) {
int cur = q.front(); q.pop();
for (auto j : squares) {
if (cur + j == n) {
return num;
} else if (cur + j < n && cnt[cur + j] == 0) {
cnt[cur + j] = num;
q.push(cur+j);
} else if (cur + j > n) break;
}
}
}
return 0;
}
};
286 Walls and Gates
You are given a m x n 2D grid initialized with these three possible values.
-1 - A wall or an obstacle. 0 - A gate. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example, given the 2D grid:
INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INFAfter running your function, the 2D grid should be:
3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4
class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
size_t m = rooms.size();
if (!m) return;
size_t n = rooms[0].size();
if (!n) return;
queue<pair<pair<int, int>, int>> q;
vector<vector<bool>> visited(rooms.size(), vector<bool>(rooms[0].size(), false));
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (rooms[i][j]==0) {
q.push({{i,j},0});
}
}
}
while (!q.empty()) {
int x_0 = q.front().first.first;
int y_0 = q.front().first.second;
int dist = q.front().second;
visited[x_0][y_0] = true;
q.pop();
if (x_0 > 0
&& rooms[x_0-1][y_0] > 0) {
if (rooms[x_0-1][y_0] > dist + 1) {
rooms[x_0-1][y_0] = dist + 1;
if (!visited[x_0-1][y_0])
q.push({{x_0-1, y_0}, rooms[x_0-1][y_0]});
}
}
if (x_0 < rooms.size() - 1 && rooms[x_0+1][y_0] > 0) {
if (rooms[x_0+1][y_0] > dist + 1) {
rooms[x_0+1][y_0] = dist + 1;
if (!visited[x_0+1][y_0])
q.push({{x_0+1, y_0}, rooms[x_0+1][y_0]});
}
}
if (y_0 > 0 && rooms[x_0][y_0-1] > 0) {
if (rooms[x_0][y_0-1] > dist + 1) {
rooms[x_0][y_0-1] = dist + 1;
if (!visited[x_0][y_0-1])
q.push({{x_0, y_0-1}, rooms[x_0][y_0-1]});
}
}
if (y_0 < rooms[0].size() -1 && rooms[x_0][y_0+1] > 0) {
if (rooms[x_0][y_0+1] > dist + 1) {
rooms[x_0][y_0+1] = dist + 1;
if (!visited[x_0][y_0+1])
q.push({{x_0, y_0+1}, rooms[x_0][y_0+1]});
}
}
}
}
};
301. Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples: "()())()" -> ["()()()", "(())()"] "(a)())()" -> ["(a)()()", "(a())()"] ")(" -> [""]
class Solution {
public:
vector<string> removeInvalidParentheses(string s) {
vector<string> res;
unordered_set<string> visited;
if (isValid(s)) return {s};
queue<string> q;
q.push(s);
visited.insert(s);
bool found = false;
while (!q.empty()) {
auto str = q.front(); q.pop();
if (isValid(str)) {
found = true;
res.push_back(str);
}
if (found) {
continue;
}
for (size_t i = 0; i < str.size(); ++i) {
if (str[i] != ')' && str[i] != '(') continue;
string next = str.substr(0, i) + str.substr(i+1);
if (visited.find(next) == visited.end()) {
q.push(next);
visited.insert(next);
}
}
}
return res;
}
bool isValid(const string& str) {
int cnt = 0;
for (auto ch : str) {
if (ch == '(') cnt++;
else if (ch == ')') {
if (--cnt < 0) return false;
}
}
return cnt == 0;
}
};
310. Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 return [1]Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 0 1 2 \ | / 3 | 4 | 5 return [3, 4]
Two solutions are the same, one is using indegree directly, the other using indegree implicitly
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (edges.size()==0) return {0};
vector<unordered_set<int>> graph(n);
queue<int> q;
// vector<int> degree(n);
for (auto edge : edges) {
// degree[edge.first]++;
// degree[edge.second]++;
graph[edge.first].insert(edge.second);
graph[edge.second].insert(edge.first);
}
for (int i = 0;i < n; ++i)
if (graph[i].size() == 1) q.push(i);
vector<int> res;
while (!q.empty()) {
int cur_len = q.size();
res.clear();
while (cur_len--) {
int v = q.front(); q.pop();
res.push_back(v);
for (auto w : graph[v]) {
graph[w].erase(v);
if (graph[w].size() == 1) q.push(w);
}
}
}
// while (!q.empty()) {
// int cur_len = q.size();
// res.clear();
// while (cur_len--) {
// int v = q.front(); q.pop();
// res.push_back(v);
// for (auto w :graph[v]) {
// if (--degree[w] == 1) q.push(w);
// }
// }
// }
return res;
}
};
317 Shortest Distance from All Buildings
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
size_t m = grid.size();
if (!m) return -1;
size_t n = grid[0].size();
if (!n) return -1;
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
vector<vector<int>> build_cnt(m, vector<int>(n, 0));
vector<pair<size_t, size_t>> allBuildings;
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (grid[i][j] == 1) allBuildings.push_back({i,j});
}
}
for (auto building : allBuildings) {
if (!bfs(grid, building.first, building.second, dist, build_cnt, allBuildings)) return -1;
}
int mindist = INT_MAX;
for (size_t i = 0; i < m; ++i) {
for (size_t j = 0; j < n; ++j) {
if (grid[i][j] == 0 && build_cnt[i][j] == allBuildings.size()) {
mindist = min(mindist, dist[i][j]);
}
}
}
return mindist == INT_MAX ? -1 : mindist;
}
bool bfs(vector<vector<int>>& grid, size_t x, size_t y, vector<vector<int>>& dist, \
vector<vector<int>>& build_cnt, vector<pair<size_t, size_t>>& allBuildings) {
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
visited[x][y] = true;
queue<pair<int, int>> q;
q.push({x, y});
int depth = 0;
vector<int> delta{1, 0, -1, 0, 1};
while (!q.empty()) {
int len = q.size();
while (len--) {
auto cur = q.front();
q.pop();
int i = cur.first, j = cur.second;
// cout << "visit : " << i << " ," << j << endl;
dist[i][j] = dist[i][j] == INT_MAX ? depth : dist[i][j] + depth;
build_cnt[i][j]++;
for (int k = 0; k < delta.size() - 1; ++k) {
int m = i + delta[k];
int n = j + delta[k + 1];
if (m >= 0 && m < grid.size() && n >= 0 && n < grid[0].size() && !visited[m][n]) {
visited[m][n] = true;
if (grid[m][n] == 0) q.push({m, n});
}
}
}
depth++;
}
for (auto building : allBuildings) {
if (!visited[building.first][building.second]) {
return false;
}
}
return true;
}
};
Rolling Ball Game
一个球从起点开始沿着通道，看能不能滚到终点。不过有限制， 每次球一走到底要不到边界，要不到障碍物，中间不能停留。 可以上下左右走，然后让写个function 给定起点， 终点，和图，判断是不是solvable. For example (1代表有障碍, 0代表可以通过):