Posts tagged as “DFS”

花花酱 LeetCode 802. Find Eventual Safe States

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/find-eventual-safe-states/description/

题目大意：给一个有向图，找出所有不可能进入环的节点。

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Idea: Finding Cycles

Solution 1: DFS

A node is safe if and only if: itself and all of its neighbors do not have any cycles.

Time complexity: O(V + E)

Space complexity: O(V + E)

// Author: Huahua

// Running time: 155 ms

class Solution {

public:

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {

vector<State> states(graph.size(), UNKNOWN);

vector<int> ans;

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

if (dfs(graph, i, states) == SAFE)

ans.push_back(i);

return ans;

}

private:

enum State {UNKNOWN, VISITING, SAFE, UNSAFE};

State dfs(const vector<vector<int>>& g, int cur, vector<State>& states) {

if (states[cur] == VISITING)

return states[cur] = UNSAFE;

if (states[cur] != UNKNOWN)

return states[cur];

states[cur] = VISITING;

for (int next : g[cur])

if (dfs(g, next, states) == UNSAFE)

return states[cur] = UNSAFE;

return states[cur] = SAFE;

}

};

Solution 1: DFS

w/o prunning TLE

w/ prunning Accepted

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

g_.clear();

for (const auto& e : flights)

g_[e[0]].emplace_back(e[1], e[2]);

vector<int> visited(n, 0);

visited[src] = 1;

int ans = INT_MAX;

dfs(src, dst, K + 1, 0, visited, ans);

return ans == INT_MAX ? - 1 : ans;

}

private:

unordered_map<int, vector<pair<int,int>>> g_;

void dfs(int src, int dst, int k, int cost, vector<int>& visited, int& ans) {

if (src == dst) {

ans = cost;

return;

}

if (k == 0) return;

for (const auto& p : g_[src]) {

if (visited[p.first]) continue; // do not visit the same city twice.

if (cost + p.second > ans) continue; // IMPORTANT!!! prunning

visited[p.first] = 1;

dfs(p.first, dst, k - 1, cost + p.second, visited, ans);

visited[p.first] = 0;

}

};

Solution 2: BFS

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

unordered_map<int, vector<pair<int,int>>> g;

for (const auto& e : flights)

g[e[0]].emplace_back(e[1], e[2]);

int ans = INT_MAX;

queue<pair<int,int>> q;

q.push({src, 0});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int curr = q.front().first;

int cost = q.front().second;

q.pop();

if (curr == dst)

ans = min(ans, cost);

for (const auto& p : g[curr]) {

if (cost + p.second > ans) continue; // Important: prunning

q.push({p.first, cost + p.second});

}

if (steps++ > K) break;

}

return ans == INT_MAX ? - 1 : ans;

}

};

Solution 3: Bellman-Ford algorithm

dp[k][i]: min cost from src to i taken up to k flights (k-1 stops)

init: dp[0:k+2][src] = 0

transition: dp[k][i] = min(dp[k-1][j] + price[j][i])

ans: dp[K+1][dst]

Time complexity: O(k * |flights|) / O(k*n^2)

Space complexity: O(k*n) -> O(n)

w/o space compression O(k*n)

C++ O(k*n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<vector<int>> dp(K + 2, vector<int>(n, kInfCost));

dp[0][src] = 0;

for (int i = 1; i <= K + 1; ++i) {

dp[i][src] = 0;

for (const auto& p : flights)

dp[i][p[1]] = min(dp[i][p[1]], dp[i-1][p[0]] + p[2]);

}

return dp[K + 1][dst] >= kInfCost ? -1 : dp[K + 1][dst];

}

};

C++ O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

constexpr int kInfCost = 1e9;

vector<int> cost(n, kInfCost);

cost[src] = 0;

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

vector<int> tmp(cost);

for (const auto& p : flights)

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2]);

cost.swap(tmp);

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

final int kInfCost = 1<<30;

int[] cost = new int[n];

Arrays.fill(cost, kInfCost);

cost[src] = 0;

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

int[] tmp = cost.clone();

for(int[] p: flights)

tmp[p[1]] = Math.min(tmp[p[1]], cost[p[0]] + p[2]);

cost = tmp;

}

return cost[dst] >= kInfCost ? -1 : cost[dst];

}

Python3

"""

Author: Huahua

Running time: 132 ms

"""

class Solution:

def findCheapestPrice(self, n, flights, src, dst, K):

kInfCost = 1e9

cost = [kInfCost for _ in range(n)]

cost[src] = 0

for i in range(K + 1):

tmp = list(cost)

for p in flights:

tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2])

cost = tmp

return -1 if cost[dst] >= 1e9 else cost[dst]

花花酱 LeetCode 784. Letter Case Permutation

By zxi on February 20, 2018

题目大意：给你一个字符串，每个字母可以变成大写也可以变成小写。让你输出所有可能字符串。

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:

Input: S = "a1b2"

Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"

Output: ["3z4", "3Z4"]

Input: S = "12345"

Output: ["12345"]

Note:

S will be a string with length at most 12.
S will consist only of letters or digits.

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<string> letterCasePermutation(string S) {

vector<string> ans;

dfs(S, 0, ans);

return ans;

}

private:

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

if (s == S.length()) {

ans.push_back(S);

return;

}

dfs(S, s + 1, ans);

if (!isalpha(S[s])) return;

S[s] ^= (1 << 5);

dfs(S, s + 1, ans);

S[s] ^= (1 << 5);

}

};

Java

// Author: Huahua

// Running time: 8 ms

class Solution {

public List<String> letterCasePermutation(String S) {

List<String> ans = new ArrayList<>();

dfs(S.toCharArray(), 0, ans);

return ans;

}

private void dfs(char[] S, int i, List<String> ans) {

if (i == S.length) {

ans.add(new String(S));

return;

}

dfs(S, i + 1, ans);

if (!Character.isLetter(S[i])) return;

S[i] ^= 1 << 5;

dfs(S, i + 1, ans);

S[i] ^= 1 << 5;

}

Python 3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def letterCasePermutation(self, S):

ans = []

def dfs(S, i, n):

if i == n:

ans.append(''.join(S))

return

dfs(S, i + 1, n)

if not S[i].isalpha(): return

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(S, i + 1, n)

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(list(S), 0, len(S))

return ans

花花酱 LeetCode 282. Expression Add Operators

By zxi on January 30, 2018

题目大意：给你一个字符串，让你在数字之间加上+,-,*使得等式的值等于target。让你输出所有满足条件的表达式。

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"]

"232", 8 -> ["2*3+2", "2+3*2"]

"105", 5 -> ["1*0+5","10-5"]

"00", 0 -> ["0+0", "0-0", "0*0"]

"3456237490", 9191 -> []

Slides:

Solution 1: DFS

Time complexity: O(4^n)

Space complexity: O(n^2) -> O(n)

C++

// Author: Huahua

// Running time: 128 ms (<79.97%)

class Solution {

public:

vector<string> addOperators(string num, int target) {

vector<string> ans;

dfs(num, target, 0, "", 0, 0, &ans);

return ans;

}

private:

void dfs(const string& num, const int target, // input

int pos, const string& exp, long prev, long curr, // state

vector<string>* ans) { // output

if (pos == num.length()) {

if (curr == target) ans->push_back(exp);

return;

}

for (int l = 1; l <= num.size() - pos; ++l) {

string t = num.substr(pos, l);

if (t[0] == '0' && t.length() > 1) break; // 0X...

long n = std::stol(t);

if (n > INT_MAX) break;

if (pos == 0) {

dfs(num, target, l, t, n, n, ans);

continue;

}

dfs(num, target, pos + l, exp + '+' + t, n, curr + n, ans);

dfs(num, target, pos + l, exp + '-' + t, -n, curr - n, ans);

dfs(num, target, pos + l, exp + '*' + t, prev * n, curr - prev + prev * n, ans);

}

};

C++ / SC O(n)

// Author: Huahua

// Running time: 13 ms (< 99.14%)

class Solution {

public:

vector<string> addOperators(string num, int target) {

vector<string> ans;

string exp(num.length() * 2, '\0');

dfs(num, target, 0, exp, 0, 0, 0, &ans);

return ans;

}

private:

void dfs(const string& num, const int target,

int pos, string& exp, int len, long prev, long curr,

vector<string>* ans) {

if (pos == num.length()) {

if (curr == target) ans->push_back(exp.substr(0, len));

return;

}

long n = 0;

int s = pos;

int l = len;

if (s != 0) ++len;

while (pos < num.size()) {

n = n * 10 + (num[pos] - '0');

if (num[s] == '0' && pos - s > 0) break; // 0X... invalid number

if (n > INT_MAX) break; // too long

exp[len++] = num[pos++];

if (s == 0) {

dfs(num, target, pos, exp, len, n, n, ans);

continue;

}

exp[l] = '+'; dfs(num, target, pos, exp, len, n, curr + n, ans);

exp[l] = '-'; dfs(num, target, pos, exp, len, -n, curr - n, ans);

exp[l] = '*'; dfs(num, target, pos, exp, len, prev * n, curr - prev + prev * n, ans);

}

};

Java

// Author: Huahua

// Running time: 16 ms (<99.17%)

class Solution {

private List<String> ans;

private char[] num;

private char[] exp;

private int target;

public List<String> addOperators(String num, int target) {

this.num = num.toCharArray();

this.ans = new ArrayList<>();

this.target = target;

this.exp = new char[num.length() * 2];

dfs(0, 0, 0, 0);

return ans;

}

private void dfs(int pos, int len, long prev, long curr) {

if (pos == num.length) {

if (curr == target)

ans.add(new String(exp, 0, len));

return;

}

int s = pos;

int l = len;

if (s != 0) ++len;

long n = 0;

while (pos < num.length) {

if (num[s] == '0' && pos - s > 0) break; // 0X...

n = n * 10 + (int)(num[pos] - '0');

if (n > Integer.MAX_VALUE) break; // too long

exp[len++] = num[pos++]; // copy exp

if (s == 0) {

dfs(pos, len, n, n);

continue;

}

exp[l] = '+'; dfs(pos, len, n, curr + n);

exp[l] = '-'; dfs(pos, len, -n, curr - n);

exp[l] = '*'; dfs(pos, len, prev * n, curr - prev + prev * n);

}

Posts tagged as “DFS”

花花酱 LeetCode 802. Find Eventual Safe States

Problem

Idea: Finding Cycles

Solution 1: DFS

Related Problems

花花酱 LeetCode 513. Find Bottom Left Tree Value

花花酱 LeetCode 787. Cheapest Flights Within K Stops

Solution 1: DFS

C++

Solution 2: BFS

C++

Solution 3: Bellman-Ford algorithm

C++ O(k*n)

C++ O(n)

Java

Python3

花花酱 LeetCode 784. Letter Case Permutation

Solution 1: DFS

C++

Java

Python 3

花花酱 LeetCode 282. Expression Add Operators

Solution 1: DFS

C++

C++ / SC O(n)

Java