Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 =
s2 =
Given:
s1 =
"aabcc"
,s2 =
"dbbca"
,
When s3 =
When s3 =
Two Dimensional DP."aadbbcbcac"
, return true.When s3 =
"aadbbbaccc"
, return false.First, if the length of s3 doesn't equal the sum of the lengths of s1 and s2, return false.
I also checked the situation where s1 or s2 is empty.
Consider any substrings of s1.substring(0, i), s2.substring(0, j) and s3.substring(0, i + j).
If s3.charAt(i + j - 1) == s1.charAt(i), then s3.substring(0, i + j - 1) should be an interleaving of s1.substring(0, i - 1) and s2.substring(0, j). Similarly, if s3.charAt(i + j - 1) == s2.charAt(j), then s3.substring(0, i + j - 1) should be an interleaving of s1.substring(0, i) and s2.substring(0, j - 1).
public class InterLeave { public boolean isInterleave(String s1, String s2, String s3) { if (s1 == null || s1.length() == 0) return s3.equals(s2); if (s2 == null || s2.length() == 0) return s3.equals(s1); if (s1.length() + s2.length() != s3.length()) return false; boolean[][] interleave = new boolean[s1.length() + 1][s2.length() + 1]; interleave[0][0] = true; for (int i = 1; i <= s1.length(); i++) { if (s3.charAt(i - 1) == s1.charAt(i - 1) && interleave[i - 1][0]) interleave[i][0] = true; } for (int j = 1; j <= s2.length(); j++) { if (s3.charAt(j - 1) == s2.charAt(j - 1) && interleave[0][j - 1]) interleave[0][j] = true; } for (int i = 1; i <= s1.length(); i++) { for (int j = 1; j <= s2.length(); j++) { if(s3.charAt(i + j - 1) == s1.charAt(i - 1) && interleave[i - 1][j] || s3.charAt(i + j - 1) == s2.charAt(j - 1) && interleave[i][j - 1]) interleave[i][j] = true; } } return interleave[s1.length()][s2.length()]; } }
No comments:
Post a Comment