[Java知识库]剑指offer05：单词长度最大乘积

**题目：**输入一个字符串数组words，请计算不包含相同字符的两个字符串word[i]和word[j]的长度， 乘积的最大值，如果所有字符串都包含至少一个相同的字符，那么返回0，假设字符串只包含英文小写字母。
分析：
方法1：用哈希表记录字符串中出现的字符， 见maxProduct方法。
方法2：用整数的二进制数位记录字符串中出现的字符。int型整数有32位，一个字符串出现的字符只需要26位，例如如果字符串包含a，则整数最右边的数是1，如果包含b那么整数的倒数第二位为1，以此类推。因此只需要与运算就可以判断字符串之间是否有重复的字符，因为如果没有重复的字符的话，两者与运算结果就是0，代码实现见方法maxProduct2。第二种方法比第一种方法效率更高，因为第一种方法判断两个字符串是否有相同的字符时可能都会判断26次，但是第二种方法只需要一次与运算就能判断是否有相同字符。

package com.wzc;

public class MaxProduct {
    /*
    *输入一个字符串数组words，请计算不包含相同字符的两个字符串word[i]和word[j]的长度
    * 乘积的最大值，如果所有字符串都包含至少一个相同的字符，那么返回0，假设字符串只包含
    * 英文小写字母
    * */
    public static void main(String[] args) {
        String[] s = {"abcw","foo","bar","fxyz","abcdef"};
        int i = maxProduct(s);
        System.out.println(i);

    }
//    用哈希表记录字符串中出现的字符
    public static int maxProduct(String[] words){
        boolean[][] flags = new boolean[words.length][26];
//        初始化每个字符串对应的哈希表word长度为n，平均每个字符串长度为k，所以时间复杂度为
//        O（nk）
//        循环每个字符串
        for (int i = 0; i < words.length; i++) {
//            遍历字符串中每个字符，在其对应的二维数组位置上令其为true
            for (char c:words[i].toCharArray()){
                flags[i][c - 'a']=true;
            }
        }
//        result记录最终要求的结果
//        根据哈希表判断每对字符串是否含有相同的字符
        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for(int j=i+1;j<words.length;j++){
                int k =0;
                for (;k<26;k++){
//                    如果第一个字符串和之后对应的字符串在26个字母中有相同的字母（前者后者对应位置都是true），循环立即终止
                    if (flags[i][k]&flags[j][k]){
                        break;
                    }
                }
//                两个字符串完全没有相同的字母
                if (k ==26){
                    int prod = words[i].length()*words[j].length();
                    result = Math.max(result,prod);
                }
            }
        }
        return result;
    }
    public static int maxProduct2(String[] words){
        int[] flags = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char ch:words[i].toCharArray()){
            //通过或运算来让字符串都标记上
               flags[i] |=1 << (ch - 'a');
            }
        }
        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j =i+1;j<words.length;j++){
//                通过与运算来确定
                if ((flags[i]&flags[j]) == 0){
                    int prod = words[i].length()*words[j].length();
                    result = Math.max(result,prod);
                }
            }
        }
        return result;
    }
}