字符串包含

题目：给定字符串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桶，将给定字符串与字典中的字符串对比即可。