Concise Java DP: Same idea of Longest Common Substring


  • 10
    Y

    The code explains itself:

    
    class Solution {
        public int findLength(int[] A, int[] B) {
            if(A == null||B == null) return 0;
            int m = A.length;
            int n = B.length;
            int max = 0;
            //dp[i][j] is the length of longest common subarray ending with nums[i] and nums[j]
            int[][] dp = new int[m + 1][n + 1];
            for(int i = 0;i <= m;i++){
                for(int j = 0;j <= n;j++){
                    if(i == 0 || j == 0){
                        dp[i][j] = 0;
                    }
                    else{
                        if(A[i - 1] == B[j - 1]){
                            dp[i][j] = 1 + dp[i - 1][j - 1];
                            max = Math.max(max,dp[i][j]);
                        }
                    }
                }
            }
            return max;
        }
    }
    

    Hope it helps!


  • 0
    B
    This post is deleted!

  • 1
    class Solution {
        public int findLength(int[] A, int[] B) {
            int max = 0;
            if (A == null || B == null) return max;
            int[][] dp = new int[A.length + 1][B.length + 1];
            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j < B.length; j++) {
                    if (A[i] == B[j]) {
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                        max = Math.max(max, dp[i + 1][j + 1]);
                    }
                }
            }
            return max;
        }
    }
    

  • 0
    J
    This post is deleted!

  • 0

    @jiaqi13 There is no [0, 1, 1] subarray in B.


  • 0
    J

    @yujun

    Very nice idea! I wasn't able to catch that this was a dp problem on my own. I've refined your solution a little

    	public int findLength(int[] A, int[] B) {
    		int m = A.length, n = B.length;
    		int counter = 0;
    //easy dynamic programming solution: is current value is a match, persist the value from immediate parent (i-1, j-1) and add 1 to it
    		int[][] dp = new int[m + 1][n + 1];
    
    		for (int i = 1; i <= m; i++) {
    			for (int j = 1; j <= n; j++) {
    				if (A[i - 1] == B[j - 1]) {
    					if (counter < (dp[i][j] = dp[i - 1][j - 1] + 1))
    						counter = dp[i][j];
    				}
    			}
    		}
    
    //		for (int[] stuff : dp) {
    //			for (int stuff1 : stuff)
    //				System.out.print(stuff1 + "|");
    //			System.out.println();
    //		}
    
    		return counter;
    	}

  • 0
    S

  • 0
    E

    More concise version:

        public int findLength(int[] A, int[] B) {
            int[][] dp = new int[A.length + 1][B.length + 1];
            int max = 0;
            for(int i  = 1; i <= A.length; i++){
                for(int j = 1; j <= B.length; j++){
                    if(A[i - 1] == B[j - 1]){
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        max = Math.max(max, dp[i][j]);
                    } 
                }
            }
            return max;
        }

Log in to reply
 

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