Posts tagged as “DFS”

花花酱 LeetCode 494. Target Sum

By zxi on January 9, 2018

题目大意：给你一串数字，你可以在每个数字前放置+或-，问有多少种方法可以使得表达式的值等于target。You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.

Output: 5

Explanation:

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Idea: DP

Solution 1: DP

Time complexity: O(n*sum)

Space complexity: O(n*sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S) return 0;

const int offset = sum;

// ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1].

vector<vector<int>> ways(n + 1, vector<int>(sum + offset + 1, 0));

ways[0][offset] = 1;

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

for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; ++j)

if (ways[i][j]) {

ways[i + 1][j + nums[i]] += ways[i][j];

ways[i + 1][j - nums[i]] += ways[i][j];

}

return ways.back()[S + offset];

}

};

C++ SC O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

for (int i = num; i < kMaxN - num; ++i)

if (ways[i]) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < S) return 0;

final int kOffset = sum;

final int kMaxN = sum * 2 + 1;

int[] ways = new int[kMaxN];

ways[kOffset] = 1;

for (final int num : nums) {

int[] tmp = new int[kMaxN];

for (int i = num; i < kMaxN - num; ++i) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

ways = tmp;

}

return ways[S + kOffset];

}

C++ / V2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

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

if (i + num < kMaxN) tmp[i] += ways[i + num];

if (i - num >= 0) tmp[i] += ways[i - num];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Solution 2: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 422 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

int ans = 0;

dfs(nums, 0, S, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int d, int S, int& ans) {

if (d == nums.size()) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d], ans);

dfs(nums, d + 1, S + nums[d], ans);

}

};

Java

// Author: Huahua

// Running time: 615 ms

class Solution {

private int ans;

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < Math.abs(S)) return 0;

ans = 0;

dfs(nums, 0, S);

return ans;

}

private void dfs(int[] nums, int d, int S) {

if (d == nums.length) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d]);

dfs(nums, d + 1, S + nums[d]);

}

Solution 3: Subset sum

Time complexity: O(n*sum)

Space complexity: O(sum)

C++ w/ copy

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

vector<int> dp(target + 1, 0);

dp[0] = 1;

for (int num : nums) {

vector<int> tmp(dp);

for (int j = 0; j <= target - num; ++j)

tmp[j + num] += dp[j];

std::swap(dp, tmp);

}

return dp[target];

}

};

C++ w/o copy

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

vector<int> dp(target + 1, 0);

dp[0] = 1;

for (int num : nums)

for (int j = target; j >= num; --j)

dp[j] += dp[j - num];

return dp[target];

}

};

花花酱 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 494. Target Sum

Idea: DP

Solution 1: DP

C++

C++ SC O(n)

Java

C++ / V2

Solution 2: DFS

C++

Java

Solution 3: Subset sum

C++ w/ copy

C++ w/o copy

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