Posts tagged as “DFS”

花花酱 LeetCode 212. Word Search II

By zxi on August 20, 2019

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.

Solution 1: DFS

Time complexity: O(sum(m*n*4^l))
Space complexity: O(l)

C++

// Author: Huahua, 708 ms, 15.3 MB

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

unordered_set<string> unique_words(words.begin(), words.end());

vector<string> ans;

for (const string& word : unique_words)

if (exist(board, word))

ans.push_back(word);

return ans;

}

private:

int w;

int h;

bool exist(vector<vector<char>> &board, string word) {

if (board.size() == 0) return false;

h = board.size();

w = board[0].size();

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

for (int j = 0 ; j < h; j++)

if (search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if (x < 0 || x == w || y < 0 || y == h || word[d] != board[y][x])

return false;

// Found the last char of the word

if (d == word.length() - 1)

return true;

char cur = board[y][x];

board[y][x] = '#';

bool found = search(board, word, d + 1, x + 1, y)

|| search(board, word, d + 1, x - 1, y)

|| search(board, word, d + 1, x, y + 1)

|| search(board, word, d + 1, x, y - 1);

board[y][x] = cur;

return found;

}

};

Solution 2: Trie

Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.

Time complexity: O(sum(l) + 4^max(l))
space complexity: O(sum(l) + l)

C++

// Author: Huahua, 64 ms, 35.6 MB

class TrieNode {

public:

vector<TrieNode*> nodes;

const string* word;

TrieNode(): nodes(26), word(nullptr) {}

~TrieNode() {

for (auto node : nodes) delete node;

}

};

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

TrieNode root;

// Add all the words into Trie.

for (const string& word : words) {

TrieNode* cur = &root;

for (char c : word) {

auto& next = cur->nodes[c - 'a'];

if (!next) next = new TrieNode();

cur = next;

}

cur->word = &word;

}

const int n = board.size();

const int m = board[0].size();

vector<string> ans;

function<void(int, int, TrieNode*)> walk = [&](int x, int y, TrieNode* node) {

if (x < 0 || x == m || y < 0 || y == n || board[y][x] == '#')

return;

const char cur = board[y][x];

TrieNode* next_node = node->nodes[cur - 'a'];

// Pruning, only expend paths that are in the trie.

if (!next_node) return;

if (next_node->word) {

ans.push_back(*next_node->word);

next_node->word = nullptr;

}

board[y][x] = '#';

walk(x + 1, y, next_node);

walk(x - 1, y, next_node);

walk(x, y + 1, next_node);

walk(x, y - 1, next_node);

board[y][x] = cur;

};

// Try all possible pathes.

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

for (int j = 0 ; j < m; j++)

walk(j, i, &root);

return ans;

}

};

花花酱 LeetCode 90. Subsets II

By zxi on May 15, 2019

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

<strong>Input:</strong> [1,2,2]

<strong>Output:</strong>

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

Solution: DFS

The key to this problem is how to remove/avoid duplicates efficiently.

For the same depth, among the same numbers, only the first number can be used.

Time complexity: O(2^n * n)
Space complexity: O(n)

C++

class Solution {

public:

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> cur;

function<void(int)> dfs = [&](int s) {

ans.push_back(cur);

if (cur.size() == n)

return;

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

if (i > s && nums[i] == nums[i - 1]) continue;

cur.push_back(nums[i]);

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 851. Loud and Rich

By zxi on May 4, 2019

In a group of N people (labelled 0, 1, 2, ..., N-1), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label x, simply “person x“.

We’ll say that richer[i] = [x, y] if person x definitely has more money than person y. Note that richer may only be a subset of valid observations.

Also, we’ll say quiet[x] = q if person x has quietness q.

Now, return answer, where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]), among all people who definitely have equal to or more money than person x.

Example 1:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

answer[7] = 7.
Among all people that definitely have equal to or more money than person 7
(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])
is person 7.

The other answers can be filled out with similar reasoning.

Note:

1 <= quiet.length = N <= 500
0 <= quiet[i] < N, all quiet[i] are different.
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]‘s are all different.
The observations in richer are all logically consistent.

Solution: DFS + Memoization

For person i , remember the quietest person who is richer than person i.

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua, running time: 108 ms, 31.6 MB

class Solution {

public:

vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {

const int n = quiet.size();

vector<vector<int>> g(n);

for (const auto& r : richer)

g[r[1]].push_back(r[0]);

vector<int> ans(n, -1);

function<void(int)> dfs = [&](int i) {

if (ans[i] != -1) return;

ans[i] = i;

for (int j : g[i]) {

dfs(j);

if (quiet[ans[j]] < quiet[ans[i]])

ans[i] = ans[j];

}

};

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

return ans;

}

};

花花酱 LeetCode 417. Pacific Atlantic Water Flow

By zxi on April 11, 2019

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter.
Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Solution: DFS/BFS

Be careful with the input range, easy to TLE with a naive implementation. Have to search from the boards.

Time complexity: O(mn)
Space complexity: O(mn)

DFS

// Author: Huahua, running time: 48 ms

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

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

const int n = matrix.size();

const int m = matrix[0].size();

vector<vector<int>> p(n, vector<int>(m));

vector<vector<int>> a(n, vector<int>(m));

for (int x = 0; x < m; ++x) {

dfs(matrix, x, 0, 0, p); // top

dfs(matrix, x, n - 1, 0, a); // bottom

}

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

dfs(matrix, 0, y, 0, p); // left

dfs(matrix, m - 1, y, 0, a); // right

}

vector<pair<int, int>> ans;

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

for (int j = 0; j < m; ++j)

if (p[i][j] && a[i][j]) ans.emplace_back(i, j);

return ans;

}

private:

void dfs(vector<vector<int>>& b, int x, int y, int h, vector<vector<int>>& v) {

if (x < 0 || y < 0 || x == b[0].size() || y == b.size()) return;

if (v[y][x] || b[y][x] < h) return;

v[y][x] = true;

dfs(b, x + 1, y, b[y][x], v);

dfs(b, x - 1, y, b[y][x], v);

dfs(b, x, y + 1, b[y][x], v);

dfs(b, x, y - 1, b[y][x], v);

}

};

BFS

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

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

const int n = matrix.size();

const int m = matrix[0].size();

const vector<int> dirs{0, 1, 0, -1, 0};

auto bfs = [&](queue<pair<int, int>>& q, vector<vector<int>>& v) {

while (!q.empty()) {

const int y = q.front().first;

const int x = q.front().second;

q.pop();

const int h = matrix[y][x];

v[y][x] = true;

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

int tx = x + dirs[i];

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

if (tx < 0 || ty < 0 || tx == m || ty == n || matrix[ty][tx] < h) continue;

if (v[ty][tx]) continue;

q.push({ty, tx});

}

};

queue<pair<int, int>> qp;

queue<pair<int, int>> qa;

vector<vector<int>> vp(n, vector<int>(m));

vector<vector<int>> va(n, vector<int>(m));

for (int x = 0; x < m; ++x) {

qp.push({0, x}); // top

qa.push({n - 1, x}); // bottom

}

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

qp.push({y, 0}); // left

qa.push({y, m - 1}); // right

}

bfs(qp, vp);

bfs(qa, va);

vector<pair<int, int>> ans;

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

for (int j = 0; j < m; ++j)

if (vp[i][j] && va[i][j]) ans.emplace_back(i, j);

return ans;

}

};

DP

// Author: Huahua, running time: 104 ms

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

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

const int n = matrix.size();

const int m = matrix[0].size();

vector<vector<int>> dp(n, vector<int>(m));

for (int x = 0; x < m; ++x) {

dp[0][x] |= 1;

dp[n - 1][x] |= 2;

}

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

dp[y][0] |= 1;

dp[y][m - 1] |= 2;

}

const vector<int> dirs{0, -1, 0, 1, 0};

while (true) {

bool changed = false;

for (int y = 0; y < n; ++y)

for (int x = 0; x < m; ++x)

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

const int tx = x + dirs[d];

const int ty = y + dirs[d + 1];

if (tx < 0 || ty < 0 || tx == m || ty == n

|| matrix[y][x] < matrix[ty][tx]

|| (dp[y][x] | dp[ty][tx]) == dp[y][x]) continue;

dp[y][x] |= dp[ty][tx];

changed = true;

}

if (!changed) break;

}

vector<pair<int, int>> ans;

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

for (int j = 0; j < m; ++j)

if (dp[i][j] == 3) ans.emplace_back(i, j);

return ans;

}

};

花花酱 LeetCode 996. Number of Squareful Arrays

By zxi on February 17, 2019

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solution1: DFS

Try all permutations with pruning.

Time complexity: O(n!)
Space complexity: O(n)

C++

// Author: Huahua, running time: 4 ms, 8.8 MB

class Solution {

public:

int numSquarefulPerms(vector<int>& A) {

std::sort(begin(A), end(A));

vector<int> cur;

vector<int> used(A.size());

int ans = 0;

dfs(A, cur, used, ans);

return ans;

}

private:

bool squareful(int x, int y) {

int s = sqrt(x + y);

return s * s == x + y;

}

void dfs(const vector<int>& A, vector<int>& cur, vector<int>& used, int& ans) {

if (cur.size() == A.size()) {

++ans;

return;

}

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

if (used[i]) continue;

// Avoid duplications.

if (i > 0 && !used[i - 1] && A[i] == A[i - 1]) continue;

// Prune invalid solutions.

if (!cur.empty() && !squareful(cur.back(), A[i])) continue;

cur.push_back(A[i]);

used[i] = 1;

dfs(A, cur, used, ans);

used[i] = 0;

cur.pop_back();

}

};

Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

Time complexity: O(n^2*2^n)
Space complexity: O(2^n)

C++

// Author: Huahua, running time: 20 ms, 14.9 MB

class Solution {

public:

int numSquarefulPerms(vector<int>& A) {

const int n = A.size();

// For deduplication.

std::sort(begin(A), end(A));

// g[i][j] == 1 if A[i], A[j] are squareful.

vector<vector<int>> g(n, vector<int>(n));

// dp[s][i] := number of ways to reach state s and ends with node i.

vector<vector<int>> dp(1 << n, vector<int>(n));

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

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

if (i == j) continue;

int r = sqrt(A[i] + A[j]);

if (r * r == A[i] + A[j])

g[i][j] = 1;

}

// For the same numbers, only the first one can be the starting point.

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

if (i == 0 || A[i] != A[i - 1])

dp[(1 << i)][i] = 1;

int ans = 0;

for (int s = 0; s < (1 << n); ++s)

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

if (!dp[s][i]) continue;

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

if (!g[i][j]) continue;

if (s & (1 << j)) continue;

// Only the first one can be used as the dest.

if (j > 0 && !(s & (1 << (j - 1))) && A[j - 1] == A[j]) continue;

dp[s | (1 << j)][j] += dp[s][i];

}

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

ans += dp[(1 << n) - 1][i];

return ans;

}

};

Posts tagged as “DFS”

花花酱 LeetCode 212. Word Search II

Solution 1: DFS

C++

Solution 2: Trie

C++

花花酱 LeetCode 90. Subsets II

C++

花花酱 LeetCode 851. Loud and Rich

C++

花花酱 LeetCode 417. Pacific Atlantic Water Flow

DFS

BFS

DP

花花酱 LeetCode 996. Number of Squareful Arrays

Solution1: DFS

C++

Solution 2: DP Hamiltonian Path

C++

Related Problems