题目：给定字符串a和b，快速判断字符串b中所有字符都在字符串a中（所有字符都为大写英文字母）
样例： a = "ABCD",b ="BAD" , 则a包含b
a = "ABCD",b = "EAB" , 则a不包含b
解法1：蛮力轮询
private static boolean contains(String a, String b) {
char[] str = a.toCharArray();
char[] subStr = b.toCharArray();
for (int i = 0; i < subStr.length; i++) {
boolean contains = false;
for (int j = 0; j < str.length; j++) {
if (subStr[i] == str[j]) {
contains = true;
break;
}
}
if (!contains) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String a = "ABCD";
String b = "DCA";
System.out.println(contains(a, b));
b = "DAE";
System.out.println(contains(a, b));
}
时间复杂度为O(mn)
解法2：先排序后轮询
private static boolean contains(String a, String b) {
char[] str = a.toCharArray();
char[] subStr = b.toCharArray();
Arrays.sort(str);
Arrays.sort(subStr);
for (int i = 0, j = 0; i < subStr.length && j < str.length; i++) {
while (j < str.length && subStr[i] != str[j]) {
j++;
}
if (j >= str.length || subStr[i] != str[j]) {
return false;
}
}
return true;
}
排序复杂度为O(mlgm)+O(nlgn)
轮询复杂度为O(m+n)
解法3：hash查找
private static boolean contains(String a, String b) {
char[] str = a.toCharArray();
char[] subStr = b.toCharArray();
int hash = 0;
for (int i = 0; i < str.length; i++) {
hash |= 1 << str[i] - 'A';
}
for (int i = 0; i < subStr.length; i++) {
if ((hash & 1 << subStr[i] - 'A') == 0) {
return false;
}
}
return true;
}
时间复杂度为O(m+n)
拓展：如何快速查找一个给定字符串在字典中的兄弟字符串。
解法：制造hash桶，将给定字符串与字典中的字符串对比即可。
