連結

797. All Paths From Source to Target
https://leetcode.com/problems/all-paths-from-source-to-target/

一開始先思考要如何簡單地找全部分支出來

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def allPathsSourceTarget(self, graph=[[4, 3, 1], [3, 2, 4], [3], [4], []]):
        loop_list = []
        for i in graph[0]:
            loop_list.append(i)
            loop_list = self.loop(graph, loop_list, [i])
            if graph[i] != []:
                loop_list.pop()
                for j in graph[i]:
                    loop_list.append(i)
                    loop_list.append(j)
                    if graph[j] != []:
                        loop_list.pop()
                        for k in graph[j]:
                            loop_list.append(j)
                            loop_list.append(k)
                            # if graph[i] != []:
                            #     loop_list.pop()
                            #     for j in graph[i]:
                            #         loop_list.append(i)
                            #         loop_list.append(j) ......

之後將他寫成 function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def allPathsSourceTarget(self, graph=[[4, 3, 1], [3, 2, 4], [3], [4], []]):
        loop_list = []
        for i in graph[0]:
            loop_list.append(i)
            loop_list = self.loop(graph, loop_list, i)
        return loop_list # [4, 3, 4, 1, 3, 4, 1, 2, 3, 4, 1, 4]
        
    def loop(self, graph, loop_list, i):
        if graph[i] != []:
            loop_list.pop()
            for j in graph[i]:
                loop_list.append(i)
                loop_list.append(j)
                loop_list = self.loop(graph, loop_list, j)
        return loop_list

將得到的結果進行處理成我們要的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def allPathsSourceTarget(self, graph=[[4, 3, 1], [3, 2, 4], [3], [4], []]):
        loop_list = []
        for i in graph[0]:
            loop_list.append(i)
            loop_list = self.loop(graph, loop_list, i)

        end_num = graph[-2][0]
        append_list = [0]
        return_list = []
        for i in loop_list:
            append_list.append(i)
            if i == end_num:
                return_list.append(append_list)
                append_list = [0]
        return return_list  # [[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4]]
        
    def loop(self, graph, loop_list, i):
        if graph[i] != []:
            loop_list.pop()
            for j in graph[i]:
                loop_list.append(i)
                loop_list.append(j)
                loop_list = self.loop(graph, loop_list, j)
        return loop_list

最後針對一些實際遇到的問題進行程式的調整

  • 有指到空的情形產生
    Input：[[4,3,1],[3,2,4],[],[4],[]]
    Output：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,4]]
    Expected：[[0,4],[0,3,4],[0,1,3,4],[0,1,4]]

  • 遇到較大輸入
    Input：[[3,1],[4,6,7,2,5],[4,6,3],[6,4],[7,6,5],[6],[7],[]]
    Output：[[0,3,6,7],[0,3,4,7],[0,4,6,7],[0,4,5,6,7],.....]
    Expected：[[0,3,6,7],[0,3,4,7],[0,3,4,6,7],[0,3,4,5,6,7],.....]

  • 遇到會回頭的輸入
    Input：[[2], [], [1]]
    Output：[[0,2,1]]
    Expected：[[0,2]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def allPathsSourceTarget(self, graph):
        end_num = len(graph)-1 # 最後要停在 len(graph)-1
        loop_list = []
        for i in graph[0]:
            loop_list.append(i)
            loop_list = self.loop(graph, loop_list, [i], end_num)

        append_list = [0]
        return_list = []
        for i in loop_list:
            if i not in append_list:
                append_list.append(i)
            if i == end_num:
                return_list.append(append_list)
                append_list = [0]
        return return_list
    
    # 較大輸入用 temp_list 去存放先前的資料
    def loop(self, graph, loop_list, temp_list, end_num):
        # 排除無效路線 temp_list[-1] != end_num
        if graph[temp_list[-1]] != [] or temp_list[-1] != end_num:
            loop_list.pop()
            for j in graph[temp_list[-1]]:
                for item in temp_list:
                    loop_list.append(item)
                temp_list.append(j)
                loop_list.append(j)
                loop_list = self.loop(graph, loop_list, temp_list, end_num)
        temp_list.pop()
        return loop_list

神人解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def allPathsSourceTarget(self, graph):
        target = len(graph) - 1
        paths, targets = [[0]], []
        while paths:
            path = paths.pop(0)
            edges = graph[path[-1]]
            if not edges: 
                continue
            for edge in edges:
                if edge==target:
                    targets.append(path+[edge])
                else:
                    paths = [path+[edge]] + paths
        return targets