ganes.kg
BAN USERHere is solution with O(m) complexity. m - Number of nodes in the larger tree.
public static boolean isSubTree(TreeNode p, TreeNode s) {
if (p == s & p == null) {
return true;
} else if (p == null || s == null) {
return false;
}
if (p.getData() == s.getData()) {
return isSubTree(p.getLeft(), s.getLeft())
&& isSubTree(p.getRight(), s.getRight());
} else {
return isSubTree(p.getLeft(), s) || isSubTree(p.getRight(), s);
}
}
public static boolean isInterleavingString(String s1, String s2, String s3) {
int p1 = 0;
int p2 = 0;
int prevStr = 0;
for (int i = 0; i < s3.length(); i++) {
if (prevStr == 0) {
if (p1 < s1.length() && s3.charAt(i) == s1.charAt(p1)) {
p1++;
} else if (p2 < s2.length() && s3.charAt(i) == s2.charAt(p2)) {
p2++;
prevStr = 1;
} else {
return false;
}
} else {
if (p2 < s2.length() && s3.charAt(i) == s2.charAt(p2)) {
p2++;
} else if (p1 < s1.length() && s3.charAt(i) == s1.charAt(p1)) {
p1++;
prevStr = 0;
} else {
return false;
}
}
}
return p1 == s1.length() && p2 == s2.length();
}
Test Cases:
isInterleavingString("aabcc", "dbbca", "aadbbcbcac") Result: true
isInterleavingString("aabcc", "dbbca", "aadbbbaccc") Result: false
Can we use the Bit Torrent protocol for transferring the large files across N machines. This is one of the way to overcome the network bandwidth constraints.
- ganes.kg January 24, 2014