leetcode BFS

本次题解包括:

  • 126 Word Ladder II
  • 127 Word Ladder
  • 130 Surrounded Regions

127 Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

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.

题目地址:leetcode Surrounded Regions

题意:给定起始和结束字符串,还有个字典,要求每次最多变化一个字母成字典里的单词,求最短的步数使得起始字符串变为结束字符串。

思路:BFS。一开始TLE了,看了DISCUSS人家是直接变换字符串!而我是比较每个单词是否差一个字母。

废话不多说。

  • 将start入队列
  • 每次取出队首(一共取当前层的长度),对队首每个字母分别进行变换(a~z),判断其是否在字典中,如果存在,加入队列。
  • 每一层结束后,将dis+1

改进版是用双向BFS,这样速度更快。

  • 和单向的不同在于,如果取出队首进行变化,变化的某一个字符串t在另一个方向的bfs中(如从start开始遍历的,而end已经遍历过t)说明有start->end的路径,将步数和累加即可。

单向的BFS

双向BFS

 

 

 

126 Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

传送门

题意:给定起始和结束字符串,还有个字典,要求每次最多变化一个字母成字典里的单词,,输出所有最短的步数使得起始字符串变为结束字符串的过程。

思路:请先做127题!

一开始是采用类似127的做法,不过每次入队列的是路径,每次取路径最后一个元素判断。结果TLE了。

后来参考别人做法,先BFS出路径,然后DFS。还是TLE了。

之后把图建出来,只要a和b相差一个字母,那么我们就建一条a->b 和b->a的边。

再进行BFS。

需要注意的是:

  • 标记使用过的单词应该这一层都遍历过才能标记,否则会出现答案不全。

 

 

130 Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

After running your function, the board should be:

题目地址:leetcode Surrounded Regions

题目大意:给定二维数组,如果一些O四周(上下左右)都是X,那么将O改为X。

思路:BFS。把O相邻的所有加入队列。如果有一个可以触碰到边界,那么说明没有全部为X,不用替换。

但其实有更简单的方法: 将边界上的点及其可达的O标记为‘A’,然后遍历board, 将A改为O, 将O改为X即可。

C++

Python

 

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode BFS
本文地址:https://www.hrwhisper.me/leetcode-bfs/

打赏一杯咖啡钱呗

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *