Search – Page 9 – Huahua’s Tech Road

花花酱 LeetCode 52. N-Queens II

By zxi on October 2, 2019

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution: DFS

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

C++

// Author: Huahua

class Solution {

public:

int totalNQueens(int n) {

vector<int> cols(n);

vector<int> diag1(2 * n - 1);

vector<int> diag2(2 * n - 1);

int ans = 0;

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

if (r == n) {

++ans;

return;

}

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

int& c = cols[i];

int& d1 = diag1[r + i];

int& d2 = diag2[r - i + n - 1];

if (c || d1 || d2) continue;

c = d1 = d2 = 1;

dfs(r + 1);

c = d1 = d2 = 0;

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 77. Combinations

By zxi on September 30, 2019

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution: DFS

Time complexity: O(C(n, k))
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> combine(int n, int k) {

vector<vector<int>> ans;

vector<int> cur;

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

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

ans.push_back(cur);

return;

}

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

cur.push_back(i + 1);

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 93. Restore IP Addresses

By zxi on September 30, 2019

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution: DFS

The range of valid numbers is [0, 255]

Time complexity: O(3^4)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> restoreIpAddresses(string s) {

vector<string> ans;

string ip;

dfs(0, s, ip, ans);

return ans;

}

private:

void dfs(int d, string s, string ip, vector<string> &ans) {

int l = s.length();

if (d == 4) {

if (l == 0) ans.push_back(ip);

return;

}

for (int i = 1; i <= min(3, s[0] == '0' ? 1 : l); i++) {

string ss = s.substr(0, i);

if (i == 3 && stoi(ss) > 255) return;

dfs(d + 1, s.substr(i), ip + (d == 0 ? "" : ".") + ss , ans);

}

};

花花酱 LeetCode 1210. Minimum Moves to Reach Target with Rotations

By zxi on September 29, 2019

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

Example 1:

Input: grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
Output: 9

Constraints:

2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.

Solution1: BFS

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

C++

// Author: Huahua, 48 ms, 18.1 MB

class Solution {

public:

inline int pos(int x, int y) {

return y * 100 + x;

}

inline int encode(int p1, int p2) {

return (p1 << 16) | p2;

}

int minimumMoves(vector<vector<int>>& grid) {

int n = grid.size();

queue<pair<int, int>> q;

unordered_set<int> seen;

q.push({pos(0, 0), pos(1, 0)}); // tail, head

seen.insert(encode(pos(0, 0), pos(1, 0)));

int steps = 0;

auto valid = [&](int x, int y) {

bool v = x >= 0 && x < n && y >= 0 && y < n && !grid[y][x];

return v;

};

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int y0 = p.first / 100;

int x0 = p.first % 100;

int y1 = p.second / 100;

int x1 = p.second % 100;

if (x0 == n - 2 && y0 == n - 1 &&

x1 == n - 1 && y1 == n - 1) {

return steps;

}

bool h = y0 == y1;

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

int tx0 = x0;

int ty0 = y0;

int tx1 = x1;

int ty1 = y1;

int rx = x0;

int ry = y0;

switch (i) {

case 0: // down

++ty0;

++ty1;

break;

case 1: // right

++tx0;

++tx1;

break;

case 2: // rotate

++rx;

++ry;

if (h) { // clockwise

--tx1;

++ty1;

} else { // counterclockwise

++tx1;

--ty1;

}

break;

}

if (!valid(tx0, ty0) || !valid(tx1, ty1) || !valid(rx, ry)) continue;

int key = encode(pos(tx0, ty0), pos(tx1, ty1));

if (seen.count(key)) continue;

seen.insert(key);

q.push({pos(tx0, ty0), pos(tx1, ty1)});

}

++steps;

}

return -1;

}

};

Solution 2: DP

dp[i][j].first = min steps to reach i,j (tail pos) facing right
dp[i][j].second = min steps to reach i, j (tail pos) facing down
ans = dp[n][n-1].first

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

C++

// Author: Huahua, 16 ms, 12.1MB

class Solution {

public:

int minimumMoves(vector<vector<int>>& grid) {

constexpr int kInf = 1e9;

const int n = grid.size();

vector<vector<pair<int, int>>> dp(n + 1,

vector<pair<int, int>>(n + 1, {kInf, kInf}));

dp[0][1].first = dp[1][0].first = -1;

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

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

bool h = false;

bool v = false;

if (!grid[i - 1][j - 1] && j < n && !grid[i - 1][j]) {

dp[i][j].first = min(dp[i - 1][j].first, dp[i][j - 1].first) + 1;

h = true;

}

if (!grid[i - 1][j - 1] && i < n && !grid[i][j - 1]) {

dp[i][j].second = min(dp[i - 1][j].second, dp[i][j - 1].second) + 1;

v = true;

}

if (v && j < n && !grid[i][j])

dp[i][j].second = min(dp[i][j].second, dp[i][j].first + 1);

if (h && i < n && !grid[i][j])

dp[i][j].first = min(dp[i][j].first, dp[i][j].second + 1);

}

return dp[n][n - 1].first >= kInf ? -1 : dp[n][n - 1].first;

}

};

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

}

};

Posts published in “Search”

花花酱 LeetCode 52. N-Queens II

Solution: DFS

C++

Related Problems

花花酱 LeetCode 77. Combinations

Solution: DFS

C++

Related Problems

花花酱 LeetCode 93. Restore IP Addresses

Solution: DFS

C++

花花酱 LeetCode 1210. Minimum Moves to Reach Target with Rotations

Solution1: BFS

C++

Solution 2: DP

C++

花花酱 LeetCode 212. Word Search II

Solution 1: DFS

C++

Solution 2: Trie

C++