[LeetCode] 718 Maximum Length of Repeated Subarray (Week 10, No.7)

Description

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

Constraints:

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

---

풀이

배열의 맨 뒤부터 값을 비교한다.
만약 두 배열의 값이 같다면 이전 위치의 값에 1을 더한게 현재 값이 된다.

dp[i][j] = dp[i+1][j+1] + 1

뒤에서부터 하나씩 앞으로 가면서 각 수가 같은지 보는데, 현재 값이 같다면 이전의 값에서 1만 더하면 되는 것이다. 그래서 dp table에 비교할 때 i와 j값이 만나는 곳에 값을 저장해서 다음으로 실행할 때 가져와서 쓴다.

---

코드

Set (Wrong Answer)

• 처음에 배열을 하나의 문자열로 만들어서, 한 문자씩 비교를 해서 여러 자리 수의 숫자에는 틀린 값이 나오게 되었다.

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // base case
        if (nums1.length == 1 && nums2.length == 1) {
            if (nums1[0] == nums2[0]) {
                return 1;
            } else {
                return 0;
            }
        }

        if (nums1.length > nums2.length)
            return allNums(nums2, nums1);
        else
            return allNums(nums1, nums2);
    }
    
    public int allNums(int[] shortArr, int[] longArr) {
        Set<String> set = new HashSet<>();
        StringBuilder longSb, shortSb;
        boolean isFind = false;
        int length = shortArr.length;

        int start;
        while (length > 0) {
            start = 0;
            for (int i = start; i <= longArr.length - length; i++) {
                longSb = new StringBuilder();
                for (int j = 0; j < length; j++) {
                    longSb.append(longArr[i + j]);
                }
                if (!set.contains(longSb.toString()))
                    set.add(longSb.toString());
            }
            length--;
        }

        System.out.println("set = " + set + "\n");


        length = shortArr.length;
        while (length > 0) {
            start = 0;

            for (int i = start; i <= shortArr.length - length; i++) {
                shortSb = new StringBuilder();
                for (int j = 0; j < length; j++) {
                    shortSb.append(shortArr[i + j]);
                }
                if (set.contains(shortSb.toString())){
                    isFind = true;
                    break;
                }
            }
            if (isFind) break;
            length--;
        }
        if (!isFind) return 0;

        return length;
    }
}

Set & HashTable (Time Limit Exceeded)

• 이번엔 배열 내의 숫자 단위로 진행하여, 해시맵에 키 = 배열의 원소 개수, 값 = 붙인 문자들(set) 으로 만들었다.
  이번에는 배열에 많은 값들이 들어왔을 때 시간초과가 발생했다.

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        // base case
        if (nums1.length == 1 && nums2.length == 1) {
            if (nums1[0] == nums2[0]) {
                return 1;
            } else {
                return 0;
            }
        }
        if (nums1.length > nums2.length)
            return allNums(nums2, nums1);
        else
            return allNums(nums1, nums2);
    }

    public int allNums(int[] shortArr, int[] longArr) {
        StringBuilder longSb, shortSb;
        boolean isFind = false;
        int length = shortArr.length;
        HashMap<Integer, Set<String>> map = new HashMap<>();

        int start;
        while (length > 0) {
            start = 0;
            for (int i = start; i <= longArr.length - length; i++) {
                longSb = new StringBuilder();
                Set<String> temp;
                for (int j = 0; j < length; j++) {
                    longSb.append(longArr[i + j]);
                }

                if (map.containsKey(length)) {
                    temp = map.get(length);
                    if (!temp.contains(longSb.toString())) {
                        temp.add(longSb.toString());
                        map.replace(length, temp);
                    }
                } else {
                    temp = new HashSet<>();
                    temp.add(longSb.toString());
                    map.put(length, temp);
                }
            }
            length--;
        }

        length = shortArr.length;
        while (length > 0) {
            start = 0;
            Set<String> temp = map.get(length);

            for (int i = start; i <= shortArr.length - length; i++) {
                shortSb = new StringBuilder();

                for (int j = 0; j < length; j++) {
                    shortSb.append(shortArr[i + j]);
                }

                if (temp.contains(shortSb.toString())) {
                    isFind = true;
                    break;
                }
            }
            if (isFind) break;
            length--;
        }
        if (!isFind) return 0;

        return length;
    }
}

DP (Accepted)

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int ans = 0;
        int[][] memo = new int[nums1.length + 1][nums2.length + 1];
        for (int i = nums1.length - 1; i >= 0; --i) {
            for (int j = nums2.length - 1; j >= 0; --j) {
                if (nums1[i] == nums2[j]) {
                    memo[i][j] = memo[i + 1][j + 1] + 1;
                    ans = Math.max(ans, memo[i][j]);
                }
            }
        }
        return ans;
    }
}