Posts published in “Search”

花花酱 LeetCode 127. Word Ladder

By zxi on September 25, 2017

https://leetcode.com/problems/word-ladder/description/

Problem:

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 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

Time Complexity: O(n*26^l) -> O(n*26^l/2), l = len(word), n=|wordList|

Space Complexity: O(n)

Solution 1: BFS

C++

// Author: Huahua

// Running time: 93 ms

class Solution {

public:

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

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

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

queue<string> q;

q.push(beginWord);

int l = beginWord.length();

int step = 0;

while (!q.empty()) {

++step;

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

string w = q.front();

q.pop();

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

char ch = w[i];

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

w[i] = j;

// Found the solution

if (w == endWord) return step + 1;

// Not in dict, skip it

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

// Remove new word from dict

dict.erase(w);

// Add new word into queue

q.push(w);

}

w[i] = ch;

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 92 ms (<76.61%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Queue<String> q = new ArrayDeque<>();

q.offer(beginWord);

int l = beginWord.length();

int steps = 0;

while (!q.isEmpty()) {

++steps;

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

String w = q.poll();

char[] chs = w.toCharArray();

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

char ch = chs[i];

for (char c = 'a'; c <= 'z'; ++c) {

if (c == ch) continue;

chs[i] = c;

String t = new String(chs);

if (t.equals(endWord)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.offer(t);

}

chs[i] = ch;

}

return 0;

}

Solution 2: Bidirectional BFS

C++

// Author: Huahua

// Running time: 32 ms (better than 96.6%)

class Solution {

public:

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

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

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

int l = beginWord.length();

unordered_set<string> q1{beginWord};

unordered_set<string> q2{endWord};

int step = 0;

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

++step;

// Always expend the smaller queue first

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

std::swap(q1, q2);

unordered_set<string> q;

for (string w : q1) {

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

char ch = w[i];

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

w[i] = j;

if (q2.count(w)) return step + 1;

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

dict.erase(w);

q.insert(w);

}

w[i] = ch;

}

std::swap(q, q1);

}

return 0;

}

};

Java

// Author: Huahua

// Running time: 31 ms (<95.17%)

class Solution {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>();

for (String word : wordList) dict.add(word);

if (!dict.contains(endWord)) return 0;

Set<String> q1 = new HashSet<>();

Set<String> q2 = new HashSet<>();

q1.add(beginWord);

q2.add(endWord);

int l = beginWord.length();

int steps = 0;

while (!q1.isEmpty() && !q2.isEmpty()) {

++steps;

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

Set<String> tmp = q1;

q1 = q2;

q2 = tmp;

}

Set<String> q = new HashSet<>();

for (String w : q1) {

char[] chs = w.toCharArray();

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

char ch = chs[i];

for (char c = 'a'; c <= 'z'; ++c) {

chs[i] = c;

String t = new String(chs);

if (q2.contains(t)) return steps + 1;

if (!dict.contains(t)) continue;

dict.remove(t);

q.add(t);

}

chs[i] = ch;

}

q1 = q;

}

return 0;

}

Python

"""

Author: Huahua

Running time: 115 ms (better than 96.84%)

"""

class Solution(object):

def ladderLength(self, beginWord, endWord, wordList):

wordDict = set(wordList)

if endWord not in wordDict: return 0

l = len(beginWord)

s1 = {beginWord}

s2 = {endWord}

wordDict.remove(endWord)

step = 0

while len(s1) > 0 and len(s2) > 0:

step += 1

if len(s1) > len(s2): s1, s2 = s2, s1

s = set()

for w in s1:

new_words = [

w[:i] + t + w[i+1:] for t in string.ascii_lowercase for i in xrange(l)]

for new_word in new_words:

if new_word in s2: return step + 1

if new_word not in wordDict: continue

wordDict.remove(new_word)

s.add(new_word)

s1 = s

return 0

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)

Related Problems

花花酱 LeetCode 675. Cut Off Trees for Golf Event

By zxi on September 14, 2017

https://leetcode.com/problems/cut-off-trees-for-golf-event/

Problem:

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

0 represents the obstacle can’t be reached.
1 represents the ground can be walked through.
The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree’s height.

You are asked to cut off all the trees in this forest in the order of tree’s height – always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can’t cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:

Input:

[

[1,2,3],

[0,0,4],

[7,6,5]

]

Output: 6

Example 2:

Input:

[

[1,2,3],

[0,0,0],

[7,6,5]

]

Output: -1

Example 3:

Input:

[

[2,3,4],

[0,0,5],

[8,7,6]

]

Output: 6

Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.

Hint: size of the given matrix will not exceed 50×50.

Idea:

Greedy + Shortest path

Identify and sort the trees by its heights, then find shortest paths between

0,0 to tree[1]
tree[1] to tree[2]
…
tree[n-1] to tree[n]

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

Space complexity: O(mn)

Solution:

// Author: Huahua

// Running time: 282 ms

class Solution {

public:

int cutOffTree(vector<vector<int>>& forest) {

m_ = forest.size();

n_ = forest[0].size();

// {height, x, y}

vector<tuple<int,int,int>> trees;

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

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

if (forest[y][x] > 1)

trees.emplace_back(forest[y][x], x, y);

// sort trees by height

sort(trees.begin(), trees.end());

int sx = 0;

int sy = 0;

int total_steps = 0;

// Move from current position to next tree to cut

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

int tx = get<1>(trees[i]);

int ty = get<2>(trees[i]);

int steps = BFS(forest, sx, sy, tx, ty);

if (steps == INT_MAX) return -1;

// Cut the tree, not necessary

forest[ty][tx] = 1;

total_steps += steps;

sx = tx;

sy = ty;

}

return total_steps;

}

private:

// min steps to go from (sx,sy) to (tx,ty) based on current map

// INT_MAX means not reachable

int BFS(const vector<vector<int>>& forest,

int sx, int sy,

int tx, int ty) {

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

auto visited = vector<vector<int>>(m_, vector<int>(n_, 0));

// {x, y}

queue<pair<int,int>> q;

q.emplace(sx, sy);

int steps = 0;

while (!q.empty()) {

int new_nodes = q.size();

while (new_nodes--) {

auto node = q.front();

q.pop();

const int cx = node.first;

const int cy = node.second;

// Found the shortest path

if (cx == tx && cy == ty)

return steps;

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

const int x = cx + dirs[i][0];

const int y = cy + dirs[i][1];

// Out of bound or unwalkable

if (x < 0 || x == n_

|| y < 0 || y == m_

|| !forest[y][x]

|| visited[y][x]) continue;

// Mark x, y as visited

visited[y][x] = 1;

q.emplace(x, y);

}

++steps;

}

// Impossible to reach

return INT_MAX;

}

int m_;

int n_;

};

花花酱 LeetCode 51. N-Queens

By zxi on September 8, 2017

Problem:

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 all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[

[".Q..", // Solution 1

"...Q",

"Q...",

"..Q."],

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

"Q...",

"...Q",

".Q.."]

]

Idea:

Solution:

Changes: 12/20/2017

type of sols_ changed from set<vector<string>> to vector<vector<string>>. Thanks to Yun-Ting Lin.

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<vector<string>> solveNQueens(int n) {

sols_.clear();

board_ = vector<string>(n, string(n, '.'));

cols_ = vector<int>(n, 0);

diag1_ = vector<int>(2 * n - 1, 0);

diag2_ = vector<int>(2 * n - 1, 0);

nqueens(n, 0);

return sols_;

}

private:

vector<string> board_;

vector<int> cols_;

vector<int> diag1_;

vector<int> diag2_;

vector<vector<string>> sols_;

bool available(int x, int y, int n) {

return !cols_[x]

&& !diag1_[x + y]

&& !diag2_[x - y + n - 1];

}

void updateBoard(int x, int y, int n, bool is_put) {

cols_[x] = is_put;

diag1_[x + y] = is_put;

diag2_[x - y + n - 1] = is_put;

board_[y][x] = is_put ? 'Q' : '.';

}

// Try to put the queen on y-th row

void nqueens(const int n, const int y) {

if (y == n) {

// found one solution, add to the ans set

sols_.push_back(board_);

return;

}

// Try every column

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

if (!available(x, y, n)) continue;

updateBoard(x, y, n, true);

nqueens(n, y + 1);

updateBoard(x, y, n, false);

}

};

花花酱 LeetCode 79. Word Search

By zxi on September 6, 2017

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

For example,
Given board =

[

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea:

Search, depth first search

Solution:

C++

class Solution {

public:

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] = 0;

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;

}

private:

int w;

int h;

};

Python

# Author: Huahua, running time: 216 ms

class Solution:

def exist(self, board: List[List[str]], word: str) -> bool:

if not board: return False

h, w = len(board), len(board[0])

def search(d: int, x: int, y: int) -> bool:

if x < 0 or x == w or y < 0 or y == h or word[d] != board[y][x]:

return False

if d == len(word) - 1: return True

cur = board[y][x]

board[y][x] = ''

found = search(d + 1, x + 1, y) or search(d + 1, x - 1, y) or search(d + 1, x, y + 1) or search(d + 1, x, y - 1)

board[y][x] = cur

return found

return any(search(0, j, i) for i in range(h) for j in range(w))

Posts published in “Search”

花花酱 LeetCode 127. Word Ladder

Solution 1: BFS

C++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems

花花酱 LeetCode 200. Number of Islands

Idea: DFS

Solution

C++

Java

Python

Related Problems

花花酱 LeetCode 675. Cut Off Trees for Golf Event

花花酱 LeetCode 51. N-Queens

花花酱 LeetCode 79. Word Search

C++

Python