华为校招实习机试&华为社招机试20240522-1.获取公共链表片段[100分]（Python3 实现100%通过率）

获取公共链表片段

给定两个链表，获取两者中相同节点值的最大连续片段。如果没有公共片段，返回-1。

解答要求

时间限制: C/C++ 1000ms,其他语言: 2000ms

内存限制: C/C++ 256MB,  其他语言: 512MB

输入

第一行表示链表1，第二行表示链表2，每条链表长度不超过20个元素，链表不会为空。

输出

公共链表片段

样例1

输入

1 2 2 3 9 1 5
9 2 2 3 6 8

输出

2 2 3

思路

数据范围小，直接模拟即可。找到第一个数组的所有子数组，放入哈希表。遍历第二个数组的所有子数组，判断是否存在于哈希表即可。

Python3代码：

nums1 = input()
nums2 = input()


st = set()
n = len(nums1)
m = len(nums2)

for i in range(n):
    for j in range(i+1,n+1):
        st.add(nums1[i:j+1])

res = ""

for i in range(m):
    for j in range(i+1,m+1):
        if nums2[i:j+1] in st and j+1-i > len(res):
            res = nums2[i:j+1]

if res:
    print(res.strip())
else:
    print(-1)