leetcode : Maximum Length of Repeated Subarray

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Maximum Length of Repeated Subarray - LeetCode

 

naive하게  풀면 O(N^3)이 나오는 문제.

딱봐도 "DP를 이용해서 O(N^2)으로 줄여라" 하는 문제다.

면접관에게 설명하듯이 화이트보드에 그림 그려가면서 혼자 설명을 해봤는데 깔끔한 dp solution을 생각해내는덴 실패했다.

결국 다른 사람의 코드를 봤다.

 

class Solution(object):
    def findLength(self, A, B):
        maxval = 0
        dp = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]
        for i in range(1, len(A) + 1):
            for j in range(1, len(B) + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    maxval = max(maxval, dp[i][j])
        return maxval

 

너무 간결해서 못 알아보기가 힘들다.

역시 리트코드 discussion..

 

나는 길이 position i,j에서 길이 k의 문자열이 일치하는걸 확인하면 i+1, j+1에서 j를 k-1만큼 스킵하고 j+k부터 검사하는걸로 생각했는데 실행시간이 빠르게 나오지 않았다.. ㅜㅠ 근데 코드도 이게 더 간결하고 보기 좋은듯.

참고로 dp[i-1]만을 참조하고 있기 때문에 space optimization이 가능하다.