Posts tagged as “DFS”

花花酱 LeetCode 753. Cracking the Safe

By zxi on December 31, 2017

题目大意：让你构建一个最短字符串包含所有可能的密码。

There is a box protected by a password. The password is n digits, where each letter can be one of the first kdigits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

Input: n = 1, k = 2

Output: "01"

Note: "10" will be accepted too.

Example 2:

Input: n = 2, k = 2

Output: "00110"

Note: "01100", "10011", "11001" will be accepted too.

Note:

n will be in the range [1, 4].
k will be in the range [1, 10].
k^n will be at most 4096.

Idea: Search

Solution 1: DFS w/ backtracking

C ++

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

string crackSafe(int n, int k) {

const int total_len = pow(k, n) + n - 1;

string ans(n, '0');

unordered_set<string> visited{ans};

if (dfs(ans, total_len, n, k, visited))

return ans;

return "";

}

private:

bool dfs(string& ans, const int total_len, const int n, const int k, unordered_set<string>& visited) {

if (ans.length() == total_len)

return true;

string node = ans.substr(ans.length() - n + 1, n - 1);

for (char c = '0'; c < '0' + k; ++c) {

node.push_back(c);

if (!visited.count(node)) {

ans.push_back(c);

visited.insert(node);

if (dfs(ans, total_len, n, k, visited)) return true;

visited.erase(node);

ans.pop_back();

}

node.pop_back();

}

return false;

}

};

Solution 2: DFS w/o backtracking

C++

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string crackSafe(int n, int k) {

const int total_len = pow(k, n) + n - 1;

string node(n - 1, '0');

string ans;

unordered_set<string> visited;

dfs(node, k, visited, ans);

return ans + node;

}

private:

void dfs(const string& node, const int k, unordered_set<string>& visited, string& ans) {

for (char c = '0'; c < '0' + k; ++c) {

string next = node + c;

if (visited.count(next)) continue;

visited.insert(next);

dfs(next.substr(1), k, visited, ans);

ans.push_back(c);

}

};

花花酱 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 301. Remove Invalid Parentheses

By zxi on December 21, 2017

Problem:

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())()"]

")(" -> [""]

题目大意：给你一个字符串，由”(” “)”和其他字符构成。让你删除数量最少的括号使得表达式合法（括号都匹配）。输出所有的合法表达式。

Idea:

Solution: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> removeInvalidParentheses(const string& s) {

int l = 0;

int r = 0;

for (const char ch : s) {

l += (ch == '(');

if (l == 0)

r += (ch == ')');

else

l -= (ch == ')');

}

vector<string> ans;

dfs(s, 0, l, r, ans);

return ans;

}

private:

bool isValid(const string& s) {

int count = 0;

for (const char ch : s) {

if (ch == '(') ++count;

if (ch == ')') --count;

if (count < 0) return false;

}

return count == 0;

}

// l/r: number of left/right parentheses to remove.

void dfs(const string& s, int start, int l, int r, vector<string>& ans) {

// Nothing to remove.

if (l == 0 && r == 0) {

if (isValid(s)) ans.push_back(s);

return;

}

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

// We only remove the first parenthes if there are consecutive ones to avoid duplications.

if (i != start && s[i] == s[i - 1]) continue;

if (s[i] == '(' || s[i] == ')') {

string curr = s;

curr.erase(i, 1);

if (r > 0 && s[i] == ')')

dfs(curr, i, l, r - 1, ans);

else if (l > 0 && s[i] == '(')

dfs(curr, i, l - 1, r, ans);

}

};

花花酱 LeetCode 749. Contain Virus

By zxi on December 18, 2017

题目大意：给你一个格子地图上面有一些病毒用1表示，未受感染的格子用0表示。带有病毒的格子每天会向四周的格子传播病毒。在每一天，你必须在最大的病毒（连通区域）的周围建造墙阻挡病毒传播。问你一共需要多少个墙才能阻挡所有病毒传播。

Problems:

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region — the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

Example 3:

Input: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.

Note:

The number of rows and columns of grid will each be in the range [1, 50].
Each grid[i][j] will be either 0 or 1.
Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

Idea:

Use DFS to find virus regions, next affected regions and # of walls needed to block each virus region.

Simulate the virus expansion process.

Solution:

C++ / DFS

Time complexity: O(n^3)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

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

int m = grid.size();

int n = grid[0].size();

int total_walls = 0;

while (true) {

vector<int> visited(m * n, 0);

vector<int> virus_area;

vector<unordered_set<int>> nexts;

int block_index = -1;

int block_walls = -1;

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

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

int key = i * n + j;

if (grid[i][j] != 1 || visited[key]) continue;

vector<int> curr;

unordered_set<int> next;

int walls = 0;

getArea(j, i, m, n, grid, visited, curr, next, walls);

if (next.empty()) continue;

if (nexts.empty() || next.size() > nexts[block_index].size()) {

virus_area.swap(curr);

block_index = nexts.size();

block_walls = walls;

}

nexts.push_back(std::move(next));

}

if (nexts.empty()) break;

total_walls += block_walls;

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

if (i == block_index) {

for (const int key : virus_area) {

int y = key / n;

int x = key % n;

grid[y][x] = 2; // blocked.

}

} else {

for (const int key : nexts[i]) {

int y = key / n;

int x = key % n;

grid[y][x] = 1; // newly affected

}

return total_walls;

}

private:

void getArea(

int x, int y, int m, int n,

vector<vector<int>>& grid,

vector<int>& visited,

vector<int>& curr,

unordered_set<int>& next,

int& walls) {

static int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == 2) return;

int key = y * n + x;

// need one wall

if (grid[y][x] == 0) {

++walls;

next.insert(key);

return;

}

if (visited[key]) return;

visited[key] = 1;

curr.push_back(key);

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

getArea(x + dirs[i][0], y + dirs[i][1], m, n, grid, visited, curr, next, walls);

}

};

Posts tagged as “DFS”

花花酱 LeetCode 753. Cracking the Safe

Idea: Search

Solution 1: DFS w/ backtracking

C ++

Solution 2: DFS w/o backtracking

C++

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

C++

Java

Python3

C++

Java

Python

花花酱 LeetCode 301. Remove Invalid Parentheses

Solution: DFS

C++

花花酱 LeetCode 749. Contain Virus

Problems:

Example 1:

Example 2:

Example 3:

Note:

Idea:

Solution:

Related Problems:

花花酱 LeetCode 742. Closest Leaf in a Binary Tree