LeetCode - Maximum Length of Repeated Subarray

문제 설명

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

입출력 예시

Example 1:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5

제약사항

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

Solution

1. Brute Force

• 이중 for문을 순회하며 같은 원소를 찾은 경우 다를때까지 index를 증가하며 비교
• O(n^3)

import java.util.*;

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int maxSubLength = 0;
	
    	
        boolean[][] dp = new boolean[nums1.length][nums2.length];

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
            
            // while문을 순회하면서 i번째와 j번째를 체크한적 있는 것은 skip
                if (dp[i][j]) {
                    continue;
                }

                int subCount = 0;
                
                // 같은 원소를 찾은 경우
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = true;

                    int trasalNum1Idx = i + 1;
                    int trasalNum2Idx = j + 1;
                    subCount = 1;
                    
                    // trasalNum1Idx와 trasalNum2Idx가 가리키는 원소가 다를때까지 while문을 순회하며 동일 subarray 길이 구함
                    while (trasalNum1Idx < nums1.length && trasalNum2Idx < nums2.length
                            && nums1[trasalNum1Idx] == nums2[trasalNum2Idx]) {
                        dp[trasalNum1Idx][trasalNum2Idx] = true;
                        subCount++;

                        trasalNum1Idx++;
                        trasalNum2Idx++;
                    }
                    maxSubLength = Math.max(maxSubLength, subCount);
                }
            }
        }
        return maxSubLength;
    }

2. DP

이중 for문을 순회하면서 값이 같은 경우, dp 배열에 저장
두 배열의 이전 인덱스 자리의 값을 중첩하며 저장

public int findLengthWithDP(int[] nums1, int[] nums2) {
        int maxSubLength = 0;

        int[][] dp = new int[nums1.length][nums2.length];

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = i>0 && j > 0 ? dp[i-1][j - 1] + 1 : 1;
                    maxSubLength = Math.max(maxSubLength, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return maxSubLength;
}