[Java] First got an idea about 3D dp and then realized that I can change it to 2D dp


  • 1
    E

    3D dp 46 ms:

        int n = s1.length();
        int m = s2.length();
        int l = s3.length();
        
        boolean[][][] dp = new boolean[l+1][n+1][m+1];
        
        for (int i = 0; i <= n; i++)
        {
        	for (int j = 0; j <= m; j++)
        		dp[0][i][j] = false;
        }
        
        dp[0][0][0] = true;
        
        for (int k = 1; k <= l; k++)
        {
        	for (int i = 0; i <= n; i++)
        	{
        		for (int j = 0; j <= m; j++)
        		{
        			dp[k][i][j] = (i+j == k)&&
        					((i >= 1 && dp[k-1][i-1][j] && s1.charAt(i-1) == s3.charAt(k-1)) 
        					|| (j >= 1 && dp[k-1][i][j-1] && s2.charAt(j-1) == s3.charAt(k-1))); 
        		}
        	}
        }
        
        return dp[l][n][m];
    

    2D dp 6ms (shrink from above solution):

        int n = s1.length();
        int m = s2.length();
        
        boolean[][] dp = new boolean[n+1][m+1];
                
        dp[0][0] = true;
        
        for (int i = 0; i <= n; i++)
    	{
    		for (int j = 0; j <= m; j++)
    		{
    			if (i == j && i == 0)
    				continue;
    			
    			int k = i+j;
    			dp[i][j] = (i >= 1 && dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k-1))
    					|| (j >= 1 && dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k-1));
    		}
    	}
                
        return dp[n][m];

  • 0

    the code can be even shorter by dp[i][j] = (i == 0 && j == 0) || (i >= 1 && dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k-1))
    || (j >= 1 && dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k-1))


Log in to reply
 

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