Posts tagged as “DFS”

花花酱 LeetCode 126. Word Ladder II

By zxi on September 26, 2017

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

[

["hit","hot","dot","dog","cog"],

["hit","hot","lot","log","cog"]

]

Note:

Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Idea:

BFS to construct the graph + DFS to extract the paths

Solutions:

C++, BFS 1

// Author: Huahua

// Running Time: 216 ms (better than 65.42%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return {};

dict.erase(beginWord);

dict.erase(endWord);

unordered_map<string, int> steps{{beginWord, 1}};

unordered_map<string, vector<string>> parents;

queue<string> q;

q.push(beginWord);

vector<vector<string>> ans;

const int l = beginWord.length();

int step = 0;

bool found = false;

while (!q.empty() && !found) {

++step;

for (int size = q.size(); size > 0; size--) {

const string p = q.front(); q.pop();

string w = p;

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

const char ch = w[i];

for (int j = 'a'; j <= 'z'; j++) {

if (j == ch) continue;

w[i] = j;

if (w == endWord) {

parents[w].push_back(p);

found = true;

} else {

// Not a new word, but another transform

// with the same number of steps

if (steps.count(w) && step < steps.at(w))

parents[w].push_back(p);

}

if (!dict.count(w)) continue;

dict.erase(w);

q.push(w);

steps[w] = steps.at(p) + 1;

parents[w].push_back(p);

}

w[i] = ch;

}

if (found) {

vector<string> curr{endWord};

getPaths(endWord, beginWord, parents, curr, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& beginWord,

const unordered_map<string, vector<string>>& parents,

vector<string>& curr,

vector<vector<string>>& ans) {

if (word == beginWord) {

ans.push_back(vector<string>(curr.rbegin(), curr.rend()));

return;

}

for (const string& p : parents.at(word)) {

curr.push_back(p);

getPaths(p, beginWord, parents, curr, ans);

curr.pop_back();

}

};

C++ / BFS 2

// Author: Huahua

// Running time: 129 ms (better than 80.67%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

vector<vector<string>> ans;

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return ans;

dict.erase(endWord);

const int l = beginWord.length();

unordered_set<string> q{beginWord}, p;

unordered_map<string, vector<string>> children;

bool found = false;

while (!q.empty() && !found) {

for (const string& word : q)

dict.erase(word);

for (const string& word : q) {

string curr = word;

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

char ch = curr[i];

for (int j = 'a'; j <= 'z'; j++) {

curr[i] = j;

if (curr == endWord) {

found = true;

children[word].push_back(curr);

} else if (dict.count(curr) && !found) {

p.insert(curr);

children[word].push_back(curr);

}

curr[i] = ch;

}

std::swap(p, q);

p.clear();

}

if (found) {

vector<string> path{beginWord};

getPaths(beginWord, endWord, children, path, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& endWord,

const unordered_map<string, vector<string>>& children,

vector<string>& path,

vector<vector<string>>& ans) {

if (word == endWord) {

ans.push_back(path);

return;

}

const auto it = children.find(word);

if (it == children.cend()) return;

for (const string& child : it->second) {

path.push_back(child);

getPaths(child, endWord, children, path, ans);

path.pop_back();

}

};

C++ / Bidirectional BFS

// Author: Huahua

// Running time: 39 ms (better than 93.74%)

class Solution {

public:

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

vector<vector<string>> ans;

unordered_set<string> dict(wordList.begin(), wordList.end());

if (!dict.count(endWord)) return ans;

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

unordered_map<string, vector<string>> children;

bool found = false;

bool backward = false;

while (!q1.empty() && !q2.empty() && !found) {

// Always expend the smaller queue first

if (q1.size() > q2.size()) {

std::swap(q1, q2);

backward = !backward;

}

for (const string& w : q1)

dict.erase(w);

for (const string& w : q2)

dict.erase(w);

unordered_set<string> q;

for (const string& word : q1) {

string curr = word;

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

char ch = curr[i];

for (int j = 'a'; j <= 'z'; j++) {

curr[i] = j;

const string* parent = &word;

const string* child = &curr;

if (backward)

std::swap(parent, child);

if (q2.count(curr)) {

found = true;

children[*parent].push_back(*child);

} else if (dict.count(curr) && !found) {

q.insert(curr);

children[*parent].push_back(*child);

}

curr[i] = ch;

}

std::swap(q, q1);

}

if (found) {

vector<string> path{beginWord};

getPaths(beginWord, endWord, children, path, ans);

}

return ans;

}

private:

void getPaths(const string& word,

const string& endWord,

const unordered_map<string, vector<string>>& children,

vector<string>& path,

vector<vector<string>>& ans) {

if (word == endWord) {

ans.push_back(path);

return;

}

const auto it = children.find(word);

if (it == children.cend()) return;

for (const string& child : it->second) {

path.push_back(child);

getPaths(child, endWord, children, path, ans);

path.pop_back();

}

};

花花酱 LeetCode 681. Next Closest Time

By zxi on September 24, 2017

Problem:

https://leetcode.com/problems/next-closest-time/description/
no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, 
which occurs 5 minutes later.  
It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. 
It may be assumed that the returned time is next day's time since it is smaller 
than the input time numerically.

Ads

Solution1: Brute force

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

set<char> s(time.begin(), time.end());

int hour = stoi(time.substr(0, 2));

int min = stoi(time.substr(3, 2));

while (true) {

if (++min == 60) {

min = 0;

(++hour) %= 24;

}

char buffer[5];

sprintf(buffer, "%02d:%02d", hour, min);

set<char> s2(buffer, buffer + sizeof(buffer));

if (includes(s.begin(), s.end(), s2.begin(), s2.end()))

return string(buffer);

}

return time;

}

};

Java

// Author: Huahua

// Running time: 85 ms

class Solution {

public String nextClosestTime(String time) {

int hour = Integer.parseInt(time.substring(0, 2));

int min = Integer.parseInt(time.substring(3, 5));

while (true) {

if (++min == 60) {

min = 0;

++hour;

hour %= 24;

}

String curr = String.format("%02d:%02d", hour, min);

Boolean valid = true;

for (int i = 0; i < curr.length(); ++i)

if (time.indexOf(curr.charAt(i)) < 0) {

valid = false;

break;

}

if (valid) return curr;

}

Python

"""

Author: Huahua

Running time: 65 ms

"""

class Solution:

def nextClosestTime(self, time):

s = set(time)

hour = int(time[0:2])

minute = int(time[3:5])

while True:

minute += 1

if minute == 60:

minute = 0

hour = 0 if hour == 23 else hour + 1

time = "%02d:%02d" % (hour, minute)

if set(time) <= s:

return time

Solution 2: DFS

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

vector<int> d = {

time[0] - '0', time[1] - '0', time[3] - '0', time[4] - '0' };

int h = d[0] * 10 + d[1];

int m = d[2] * 10 + d[3];

vector<int> curr(4, 0);

int now = toTime(h, m);

int best = now;

dfs(0, d, curr, now, best);

char buff[5];

sprintf(buff, "%02d:%02d", best / 60, best % 60);

return string(buff);

}

private:

void dfs(int dep, const vector<int>& digits, vector<int>& curr, int time, int& best) {

if (dep == 4) {

int curr_h = curr[0] * 10 + curr[1];

int curr_m = curr[2] * 10 + curr[3];

if (curr_h > 23 || curr_m > 59) return;

int curr_time = toTime(curr_h, curr_m);

if (timeDiff(time, curr_time) < timeDiff(time, best))

best = curr_time;

return;

}

for (int digit : digits) {

curr[dep] = digit;

dfs(dep + 1, digits, curr, time, best);

}

int toTime(int h, int m) {

return h * 60 + m;

}

int timeDiff(int t1, int t2) {

if (t1 == t2) return INT_MAX;

return ((t2 - t1) + 24 * 60) % (24 * 60);

}

};

Solution 3: Brute force + Time library

Python3

"""

Author: Huahua

Running time: 292 ms

"""

from datetime import *

class Solution:

def nextClosestTime(self, time):

s = set(time)

while True:

time = (datetime.strptime(time, '%H:%M') +

timedelta(minutes=1)).strftime('%H:%M')

if set(time) <= s:

return time

Solution: DFS

C++

// Author: Huahua

// Time complexity: O(n^2)

// Space complexity: O(n)

// Running Time: 25 ms

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

if (M.empty()) return 0;

int n = M.size();

int ans = 0;

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

if (!M[i][i]) continue;

++ans;

dfs(M, i, n);

}

return ans;

}

private:

void dfs(vector<vector<int>>& M, int curr, int n) {

// Visit all friends (neighbors)

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

if (!M[curr][i]) continue;

M[curr][i] = M[i][curr] = 0;

dfs(M, i, n);

}

};

Java

// Author: Huahua

// Time complexity: O(n^2)

// Space complexity: O(n)

// Running Time: 20 ms

class Solution {

public int findCircleNum(int[][] M) {

int n = M.length;

if (n == 0) return 0;

int ans = 0;

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

if (M[i][i] == 0) continue;

++ans;

dfs(M, i, n);

}

return ans;

}

private void dfs(int[][] M, int curr, int n) {

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

if (M[curr][i] == 0) continue;

M[curr][i] = M[i][curr] = 0;

dfs(M, i, n);

}

Python

"""

Author: Huahua

Time complexity: O(n^2)

Space complexity: O(n)

Running Time: 162 ms

"""

class Solution(object):

def findCircleNum(self, M):

"""

:type M: List[List[int]]

:rtype: int

"""

def dfs(M, curr, n):

for i in xrange(n):

if M[curr][i] == 1:

M[curr][i] = M[i][curr] = 0

dfs(M, i, n)

n = len(M)

ans = 0

for i in xrange(n):

if M[i][i] == 1:

ans += 1

dfs(M, i, n)

return ans

Solution 2: Union Find

C++

// Author: Huahua

// Runtime: 19 ms

class UnionFindSet {

public:

UnionFindSet(int n) {

parents_ = vector<int>(n + 1, 0);

ranks_ = vector<int>(n + 1, 0);

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

parents_[i] = i;

}

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pu] > ranks_[pv]) {

parents_[pv] = pu;

} else if (ranks_[pv] > ranks_[pu]) {

parents_[pu] = pv;

} else {

parents_[pu] = pv;

++ranks_[pv];

}

return true;

}

int Find(int id) {

if (id != parents_[id])

parents_[id] = Find(parents_[id]);

return parents_[id];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

class Solution {

public:

int findCircleNum(vector<vector<int>>& M) {

int n = M.size();

UnionFindSet s(n);

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

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

if (M[i][j] == 1) s.Union(i, j);

unordered_set<int> circles;

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

circles.insert(s.Find(i));

return circles.size();

}

};

Idea: DFS

Use DFS to find a connected component (an island) and mark all the nodes to 0.

Time complexity: O(mn)

Space complexity: O(mn)

Solution

C++

// Author: Huahua

// Time complexity: O(mn)

// Running time: 6 ms

class Solution {

public:

int numIslands(vector<vector<char>>& grid) {

if (grid.empty()) return 0;

int m = grid.size();

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

int ans = 0;

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

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

ans += grid[y][x] - '0';

dfs(grid, x, y, m, n);

}

return ans;

}

private:

void dfs(vector<vector<char>>& grid, int x, int y, int m, int n) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, m, n);

dfs(grid, x - 1, y, m, n);

dfs(grid, x, y + 1, m, n);

dfs(grid, x, y - 1, m, n);

}

};

Java

// Author: Huahua

// Time Complexity: O(mn)

// Running time: 13 ms

class Solution {

public int numIslands(char[][] grid) {

int m = grid.length;

if (m == 0) return 0;

int n = grid[0].length;

int ans = 0;

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

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

if (grid[y][x] == '1') {

++ans;

dfs(grid, x, y, n, m);

}

return ans;

}

private void dfs(char[][] grid, int x, int y, int n, int m) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, n, m);

dfs(grid, x - 1, y, n, m);

dfs(grid, x, y + 1, n, m);

dfs(grid, x, y - 1, n, m);

}

Python

"""

Author: Huahua

Time Complexity: O(mn)

Running Time: 102 ms

"""

class Solution(object):

def numIslands(self, grid):

"""

:type grid: List[List[str]]

:rtype: int

"""

m = len(grid)

if m == 0: return 0

n = len(grid[0])

ans = 0

for y in xrange(m):

for x in xrange(n):

if grid[y][x] == '1':

ans += 1

self.__dfs(grid, x, y, n, m)

return ans

def __dfs(self, grid, x, y, n, m):

if x < 0 or y < 0 or x >=n or y >= m or grid[y][x] == '0':

return

grid[y][x] = '0'

self.__dfs(grid, x + 1, y, n, m)

self.__dfs(grid, x - 1, y, n, m)

self.__dfs(grid, x, y + 1, n, m)

self.__dfs(grid, x, y - 1, n, m)

Posts tagged as “DFS”

花花酱 LeetCode 126. Word Ladder II

花花酱 LeetCode 681. Next Closest Time

Problem:

Example 1:

Example 2:

Solution1: Brute force

C++

Java

Python

Solution 2: DFS

C++

Solution 3: Brute force + Time library

Python3

Related Problems:

花花酱 LeetCode 547. Friend Circles

Solution: DFS

C++

Java

Python

Solution 2: Union Find

C++

Related Problems

花花酱 LeetCode 200. Number of Islands

Idea: DFS

Solution

C++

Java

Python

Related Problems

花花酱 LeetCode 637. Average of Levels in Binary Tree