题目描述:
LeetCode 718. Maximum Length of Repeated Subarray
Given two integer arrays A
and B
, return the maximum length of an subarray that appears in both arrays.
Example 1:
Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].
Note:
- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
题目大意:
给定整数数组A和B,求其最长公共连续子串。
解题思路:
动态规划(Dynamic Programming)
dp[i][j]表示A串中第i个字符,B串中第j个字符结尾的最长公共子串的长度
状态转移方程
dp[i][j] = dp[i - 1][j - 1] + 1 if A[i] == B[j] dp[i][j] = 0 otherwise
上式的空间复杂度可以使用滚动数组优化为一维
Python代码:
class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
sa, sb = len(A), len(B)
dp = [0] * sb
ans = 0
for x in range(sa):
ndp = [0] * sb
for y in range(sb):
if A[x] == B[y]:
ndp[y] = 1
if x and y:
ndp[y] += dp[y - 1]
ans = max(ans, ndp[y])
dp = ndp
return ans
比赛中尝试了Trie和KMP的解法,但是均返回Time Limit Exceeded
Trie树解法(Time Limit Exceeded)
Python代码:
class TrieNode:
def __init__(self):
self.children = dict()
class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
sa, sb = len(A), len(B)
root = TrieNode()
for x in range(sa):
node = root
for y in range(x, sa):
num = A[y]
child = node.children.get(num)
if child is None:
child = TrieNode()
node.children[num] = child
node = child
ans = 0
for x in range(sb):
cnt = 0
node = root
for y in range(x, sb):
num = B[y]
node = node.children.get(num)
if node is None: break
cnt += 1
ans = max(ans, cnt)
return ans
KMP解法(Time Limit Exceeded)
Python代码:
class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
sa, sb = len(A), len(B)
ans = 0
for x in range(sa):
size = sa - x
next = [0] * size
for i in range(1, size):
k = next[i - 1]
while A[i + x] != A[k + x] and k:
k = next[k - 1]
if A[i + x] == A[k + x]:
next[i] = k + 1
z = 0
for y in range(sb):
if z >= size: break
while z and A[z + x] != B[y]:
z = next[z - 1]
if A[z + x] == B[y]:
z += 1
ans = max(ans, z)
return ans
本文链接:http://bookshadow.com/weblog/2017/10/29/leetcode-maximum-length-of-repeated-subarray/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。