Similar to LCS


  • 0
    P
    class Solution(object):
        def findLength(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: int
            """
            # idea is similar to finding longest common substring
            
            n, m = len(A), len(B)
            if n == 0 or m == 0: # if either of the array is empty max. repeated array is 0
                return 0
            max_repeated_arr = 0
            S = [[0 for mi in range(m+1)] for ni in range(n+1)]
            # print(S)
            for ni in range(n+1):
                for mi in range(m+1):
                    if ni == 0 or mi == 0:
                        S[ni][mi] = 0
                    else:
                        if A[ni-1] == B[mi-1]:
                            S[ni][mi] = 1 + S[ni-1][mi-1]
                            max_repeated_arr = max(max_repeated_arr, S[ni][mi])
            # print(S)
            return max_repeated_arr        
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.