预处理在快速判断两个单词是否有相同字符的应用

判断两个单词是否有相同字符，一般的做法是，采用辅助的集合类容器，先遍历一个字符串，把它的字符放到集合中；再遍历第二个字符串，检查其字符是否存在于集合。时间复杂度是O(len1 + len2)。len1, len2 分别是两个字符串的长度。

如果是一个单词的集合，需要判断两两判断两个单词是否有重复字符，按照上面的算法，总的复杂度变为 O(n * len), len是字符串长度的上限。

其实这种情况，可以对字符串进行预处理（离线算法的思想），使得判断两个单词是否有相同字符变为一个O(1)的操作。这里面利用到单词的字符集是有限的这一特性，比如，英文单词就是26个字母，可以把一个单词包含的字母的情况，转化为一个26位的位图，两个单词如果有相同的字母，那么相应的bit位置上就同为1。把位图当成一个数，两个位图做一个“与”操作，结果为0就得出对应的单词无重复字符。

例题：Leetcode 剑指 Offer II 005
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。、

class Solution {
    public int maxProduct(String[] words) {
        int[] masks = new int[words.length];
        for (int i = 0; i < words.length; ++i) {
            for (int k = 0; k < words[i].length(); ++k) {
                masks[i] |= 1 << words[i].charAt(k) - 'a';
            }
        }
        int len = 0;
        for (int i = 0; i < words.length; ++i) {
            for (int j = i + 1; j < words.length; ++j) {
                if ((masks[i] & masks[j]) == 0) {
                    len = Math.max(len, words[i].length() * words[j].length());
                }
            }
        } 
        return len;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19