Untitled
unknown
plain_text
a year ago
2.1 kB
3
Indexable
class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n = s1.length(); int m = s2.length(); int p = s3.length(); if (n + m != p) { return false; } boolean[][][] dp = new boolean[n + 1][m + 1][p + 1]; dp[0][0][0] = true; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 1; k <= p; k++) { if (i > 0 && s1.charAt(i - 1) == s3.charAt(k - 1)) { dp[i][j][k] = dp[i][j][k] || dp[i - 1][j][k - 1]; } if (j > 0 && s2.charAt(j - 1) == s3.charAt(k - 1)) { dp[i][j][k] = dp[i][j][k] || dp[i][j - 1][k - 1]; } } } } return dp[n][m][p]; // for (int[][] array : dp) { // for (int[] arr : array) { // Arrays.fill(arr, -1); // } // } // dp[0][0][0] = 1; // return isInterLeave(n,m,p, s1, s2, s3, dp); } private boolean isInterLeave(int i, int j, int k, String s1, String s2, String s3, int[][][] dp) { if (k == 0 && i == 0 && j == 0) { return true; } if (k <= 0 && (i > 0 || j > 0)) { return false; } if (dp[i][j][k] != -1) { boolean val = (dp[i][j][k] == 0) ? false : true; return val; } if (i > 0 && s1.charAt(i - 1) == s3.charAt(k - 1)) { if (isInterLeave(i - 1, j, k - 1, s1, s2, s3, dp)) { dp[i][j][k] = 1; return true; } } if (j > 0 && s2.charAt(j - 1) == s3.charAt(k - 1)) { if (isInterLeave(i, j - 1, k - 1, s1, s2, s3, dp)) { dp[i][j][k] = 1; return true; } } dp[i][j][k] = 0; return false; } }
Editor is loading...
Leave a Comment