Karat 002 Longest Common Continuous Subarray

[
[“3234.html”, “xys.html”, “7hsaa.html”], // user1
[“3234.html”, “sdhsfjdsh.html”, “xys.html”, “7hsaa.html”] // user2
]

输出两个user的最长连续且相同的访问记录。

题目大意：

求连续最长子数组

解题思路：

类似于LeetCode 1143先求最长公共子字符串。

LeetCode 1143 Longest Common Subsequence, 求最长公共子字符串
Karat 002 Longest Common Continuous Subarray 一样的题目，结果类型不同：最长长度和结果

不同之处在于：

1. 由于是连续，所以递归只有相同的情况，其他情况为0。
2. 答案不是最后一位，而是全局最值

递归式为

dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
         = 0

解题步骤：

N/A

注意事项：

1. 递归只有一种情况
2. 答案需求全局

Python代码：

# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = 0
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				res = max(res, dp[i][j])
	return res

优化空间：

def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

回到原题，输入是列表而不是字符串，但原理一样。还有需要输出公共结果，而不是数字

Python代码：

def longestCommonContinuousSubarray(self, history1, history2):
	dp = [[0 for _ in range(len(history2) + 1)] for _ in range(len(history1) + 1)]
	max_len, res = 0, []
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if history1[i - 1] == history2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				if dp[i][j] > max_len:
					max_len = dp[i][j]
					res = history1[i - dp[i][j]:i]
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)