Graph Flashcards
- Word Ladder II
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.
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.
Example 1:
Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] Example 2:
Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: []
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
先用BFS找到最短路徑，並且每個node都存他最短路徑的parent。之後再用DFS根據parent去找出path
BFS two end build graph and directly get path
BFS
Build graph (dict or list or no need)
init queue
while q:
for I in xrange(len(q)): # use or not depends on if you need level info or not.
cur - q.pop(0)
for nei in graph[cur]:- Word Ladder
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.
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.
Example 1:
~~~
Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Example 2:
~~~
Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
~~~
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
~~~
BFS
add visited when append new node(fast). not when pop node(slow.
init queue
init visited
while q
cur q.pop
for I in len(cur):
for c in 'abcd....'
if new_word in wordSet:
q. append
visited. add(new_word)
Bi-BFS
其實差別只要多一個queue，並且step試用累加的不是存在queue，如果next_node出現在q2那就表示遇到了，return step + 1，還要替換q1, q2，這邊要注意visited裡面已經存有q2看過的node，所以在看new_word是否在q2之前不可以先if new_word in visited: continue，這樣就會造成跳過
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
“””
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
“””
# No need to build graph
wordSet = set(wordList)
if endWord not in wordSet: return 0
q1, q2 = [beginWord], [endWord]
step = 0
visited = set([beginWord, endWord])
while q1:
step += 1
for _ in range(len(q1)):
cur = q1.pop(0)
for i in xrange(len(cur)): # These two for loop is used to find the neighbor
for c in ‘abcdefghijklmnopqrstuvwxyz’:
if c == cur[i]: continue
new_word = cur[:i] + c + cur[i+1:]
if new_word in q2: return step + 1
if new_word in visited: continue
if new_word in wordSet:
q1.append(new_word)
visited.add(new_word)
if len(q1) > len(q2):
q1, q2 = q2, q1
return 0
- Course Schedule
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
~~~
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
~~~
Example 2:
~~~
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
~~~
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
這題不適一個正常的BFS，他不會把所有的neighbor append到queue裡面，只有indegree == 0的才會，有條件的BFS走法。一開始的queue也不適從只有[root]開始，而是很多個indegree == 0的node，貫徹topoolgical sort的概念，我只從indegree==0的開始走。
記錄每個vertex的indegree(進入的edge數目)，只從indegree==0的vertex去走，走過一條edge就把下個vertex的indegree -= 1，如果有cycle，那cycle裡面的vertex一定indegree至少=1，所以就沒辦法進入cycle去減大家的indegree，這樣他們的一定不=0。
想不起來要從indegree=0的開始，BFS
並且並不會從node的children繼續開始，而是繼續找indegree=0的
DFS 沒個node都開始dfs一次 用visited去紀錄每個node的狀態 0 -> 沒去過 1 -> 看過 -1 ->看過並且是我的parent
n = numCourses
graph = [[] for i in xrange(n)]
visited = [0 for i in xrange(n)]
for p in prerequisites:
graph[p[1]].append(p[0])
ans = True
for i in xrange(n):
if not self.dfs(graph, visited, i): return False
return True
def dfs(self, graph, visited, index):
if visited[index] == -1: return False
if visited[index] == 1: return True
visited[index] = -1
for j in graph[index]:
if not self.dfs(graph, visited, j): return False
visited[index] = 1
return True
- Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
~~~
Input: 2, [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished
course 0. So the correct course order is [0,1] .
~~~
Example 2:
~~~
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both
courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
~~~
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
BFS indegree 跟207題差不多，只是這邊多存一下路徑，其實只要照這queue從indegree==0的課開始上就一定是valid的path
