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

• 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];``````

• 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))

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