For example,
Given:
s1 =
"aabcc"
,s2 =
"dbbca"
,
When s3 =
"aadbbcbcac"
, return true.When s3 =
"aadbbbaccc"
, return false.
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { // DP problem int n1 = s1.length(); int n2 = s2.length(); int n3 = s3.length(); if (n1 + n2 != n3) return false; // match[i][j] represents if the first (i+j) elements of s3 can be interleaved by the first i elements of s1 and the first j // elements of s2 boolean[][] match = new boolean[n1+1][n2+1]; match[0][0] = true; // If s2 is null && s3 == s1 for(int i = 1; i <= n1; i++) { if (s3.charAt(i-1) == s1.charAt(i-1)) match[i][0] = true; else break; } // If s1 is null && s3 == s2 for (int i = 1; i <= n2; i++) { if (s3.charAt(i-1) == s2.charAt(i-1)) match[0][i] = true; else break; } for (int i = 1; i <= n1; i++) { char c1 = s1.charAt(i-1); for (int j = 1; j <= n2; j++) { char c2 = s2.charAt(j-1); char c3 = s3.charAt(i+j-1); // e.g., s1 --- "xxx$", s2 --- "###", s3 --- "@@@@@@$" // Here c1==c3 is true, if "xxx" and "###" can interleave "@@@@@@", s1 and s2 can also interleave s3. if (c1 == c3) match[i][j] = match[i-1][j]; // Note: "||" indicates if match[i][j] has already be true, it will still be true. if (c2 == c3) match[i][j] = match[i][j] || match[i][j-1]; } } return match[n1][n2]; } }
No comments:
Post a Comment