fun findLength(nums1: IntArray, nums2: IntArray): Int {
var max = 0
for (i in 0 until nums1.size) {
for (j in 0 until nums2.size) {
var k = 0
// Find the common subarray, it takes O(m * n * min(m, n)) = O(n^3)
while (i + k < nums1.size && j + k < nums2.size && nums1[i + k] == nums2[j + k]) {
k++
max = if (k > max) k else max
}
}
}
return max
}
It's LCS variant, here we're looking for the longest common subarray (not subsequence), it has the optimal substructure: dp[i][j] = 1 + dp[i - 1][j - 1]
when A[i] == B[j]
.
But the difference between subsequence and subarray is that it must be continuous for subarray, so dp[i][j] = 0
when A[i] != B[j]
.
fun findLength(nums1: IntArray, nums2: IntArray): Int {
val m = nums1.size
val n = nums2.size
val dp = Array(m + 1) { _ -> IntArray(n + 1) }
var max = 0
for (i in 0 until m) {
dp[i][0] = 0
}
for (j in 0 until n) {
dp[0][j] = 0
}
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = if (nums1[i - 1] == nums2[j - 1]) {
1 + dp[i - 1][j - 1]
} else {
0
}
max = if (dp[i][j] > max) dp[i][j] else max
}
}
return max
}
- Time Complexity:
O(m * n)
wherem
andn
are the length of two strings, respectively. - Space Complexity:
O(m * n)
for 2D dp array.
Since every dp[i][j]
depends only on dp[i - 1][j - 1]
, we can store as dp[2][j]
for space optimization.
j, j+1
i X
\
i+1 Y
n1 = "23"
n2 = "123"
0, 1, 2, 3 // index
0 0 X
1 Y // Y depends on X
2 Z // Z depends on Y
// So we store for X, Y row, then shift to Y, Z row.
fun findLength(nums1: IntArray, nums2: IntArray): Int {
// TODO: Here we should use the shorter array as the first array to reduce the space complexity.
val dp = Array(2) { IntArray(nums2.size + 1) { 0 }
val max = 0
for (i in 1..nums1.size) {
for (j in 1..nums2.size) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[0][j] = 1 + dp[1][j - 1]
}
max = maxOf(max, dp[0][j])
}
// shift dp[1] to dp[0]
for (j in 0..nums2.size) {
dp[1][j] = dp[0][j]
// This is nessary to clean up the value of dp[0][j] for next iteration.
dp[0][j] = 0
}
}
return max
}
- Time Complexity:
O(m * n)
wherem
andn
are the length of two strings, respectively. - Space Complexity:
O(min(n, n)
.