小黑回了一波儿血，抽空想了想KMP的leetcode之旅：1367. 二叉树中的列表（在操场上看到了中老黑牵手）

小黑尝试编写KMP算法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        # 生成NEXT数组
        def getNext(patt):
            i = 1
            prefix_len = 0
            next_ = [0]
            while i < len(patt):
                if patt[i] == patt[prefix_len]:
                    i += 1
                    prefix_len += 1
                    next_.append(prefix_len)
                else:
                    if prefix_len == 0:
                        next_.append(0)
                        i += 1
                    else:
                        prefix_len = next_[prefix_len-1]
            return next_
        # KMP匹配
        def kmp_search(patt,string):
            i = 0
            j = 0
            next_ = self.next_
            while i < len(string):
                if string[i] == patt[j]:
                    i += 1
                    j += 1
                else:
                    if j == 0:
                        i += 1
                    else:
                        j = next_[j-1]
                if j == len(patt):
                    return True
            return False
        
        def dfs(node,path):
            if not node:
                return False
            path.append(node.val)
            # print(path)
            if not (node.left or node.right):
                result = kmp_search(patt,path)
                path.pop()
                return result
            result = dfs(node.left,path) or dfs(node.right,path)
            path.pop()
            return result
        patt = []
        while head:
            patt.append(head.val)
            head = head.next
        self.next_ = getNext(patt)
        
        return dfs(root,[])
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

仿照网上的大神代码(看了将近一天，理解了80%,自己实现一遍)，小黑无法一步登天，这道题先这样。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:

        # 获得next数组
        def get_next(head):
            p = ListNode(next = head)
            i = -1
            next_ = [p]
            next_i = [i]
            while head.next:
                if i == -1 or p.val == head.val:
                    head = head.next
                    p = p.next
                    i += 1
                    next_i.append(i)
                    next_.append(p)
                else:
                    p = next_[i]
                    i = next_i[i]
            return next_,next_i
        
        def matchNode(head,node,i):

            while head.val != node.val:
                head = self.next_[i]
                i = self.next_i[i]
                if i == -1:
                    break
            return head.next,i+1
        def dfs(head,node,i):
            if not head:
                return True
            if not node:
                return False
            head,i = matchNode(head,node,i)
            return dfs(head,node.left,i) or dfs(head,node.right,i)
        self.next_,self.next_i = get_next(head)
        print(self.next_i)
        return dfs(head,root,0)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

小黑自己一通乱改，总算出来了，虽然自己不是很理解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:

        # 获得next数组
        def get_next(head):
            i = 1
            prefix_len = 0
            next_ = [0]
            arr = []
            while head:
                arr.append(head)
                head = head.next
            while i < len(arr):
                if arr[i].val == arr[prefix_len].val:
                    prefix_len += 1
                    i += 1
                    next_.append(prefix_len)
                else:
                    if prefix_len == 0:
                        next_.append(0)
                        i += 1
                    else:
                        prefix_len = next_[prefix_len-1]
            return arr,next_

        
        def matchNode(head,node,i):

            while head.val != node.val:
                if i == 0:
                    return self.arr[i],i
                i = self.next_[i-1]
                head = self.arr[i]
            return head.next,i+1

            return self.arr[i],i
        def dfs(head,node,i):
            if not head:
                return True
            if not node:
                return False
            head,i = matchNode(head,node,i)
            return dfs(head,node.left,i) or dfs(head,node.right,i)
        self.arr,self.next_ = get_next(head)
        return dfs(head,root,0)
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

小黑生活