Press "Enter" to skip to content

Posts published in “Search”

花花酱 LeetCode 127. Word Ladder

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:

  1. Only one letter can be changed at a time.
  2. 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++

Java

Solution 2: Bidirectional BFS

C++

Java

Python

Related Problems

花花酱 LeetCode 200. Number of Islands

Problem:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

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++

Java

Python

Related Problems

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

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:

  1. 0 represents the obstacle can’t be reached.
  2. 1 represents the ground can be walked through.
  3. 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:

Example 2:

Example 3:

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:

 

花花酱 LeetCode 51. N-Queens

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:

Idea:
Search
Solution:
Changes: 12/20/2017
type of sols_ changed from set<vector<string>> to vector<vector<string>>. Thanks to Yun-Ting Lin.

 

花花酱 LeetCode 79. Word Search

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 =

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

Idea:
Search, depth first search
Solution:

C++



Python