LCR005.最大单词长度乘积

剑指offer（专项突破版）1.2 二进制

题目链接：LCR005-最大单词长度乘积

方法1：用哈希表记录字符串中出现的字符

分析：蛮力。对每一个字符串，存储一个记录每个字符的哈希表；对每个字符串对，比较其哈希表。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        // 定义哈希表
        bool table[1000][26] = {false};
        // 记录每个字符串包含字符的情况
        for(int i = 0;i < words.size();i++){
            for(int j = 0;j < words[i].length();j++){
                string word = words[i];
                int index = word[j] - 'a';
                table[i][index] = true;
            }
        }
        //记录最大值
        int res = 0;
        // 每一对字符串的情况
        for(int i = 0;i < words.size()-1;i++){
            for(int j = i+1;j < words.size();j++){
                int k;
                for(k = 0;k < 26;k++){
                    if(table[i][k] && table[j][k]){
                        break;
                    }
                }
                // 找到不包含相同字符的两个字符串
                if(k == 26){
                    int temp = words[i].length()*words[j].length();
                    if(temp > res){
                        res = temp;
                    }
                }
            }
        }
        return res;
    }
};

时间复杂度分析： 第1步，初始化每个字符串对应的哈希表。如果数组words的长度为n，平均每个字符串的长度为k，那么初始化哈希表的时间复杂度是O（n_k）。第2步，根据哈希表判断每对字符串是否包含相同的字符。总共有O（n₂）对字符串，判断每对字符串是否包含相同的字符需要的时间为O（1），因此这一步的时间复杂度是O（n₂）。于是这种解法的总体时间复杂度是O（n_k+n₂）。

结果：

方法2：用整数的二进制数位记录字符串中出现的字符

分析：可以用一个int型整数记录某个字符串中出现的字符。如果字符串中包含’a’，那么整数最右边的数位为1；如果字符串中包含’b’，那么整数的倒数第2位为1，其余以此类推。这样做的好处是能更快地判断两个字符串是否包含相同的字符。如果两个字符串中包含相同的字符，那么它们对应的整数相同的某个数位都为1，两个整数的与运算将不会等于0。如果两个字符串没有相同的字符，那么它们对应的整数的与运算的结果等于0。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        // 定义哈希表
        int table[1000] = {0};
        // 记录每个字符串包含字符的情况
        for(int i = 0;i < words.size();i++){
            for(int j = 0;j < words[i].length();j++){
                string word = words[i];
                int index = word[j] - 'a';
                table[i] |= 1 << index;
            }
        }
        //记录最大值
        int res = 0;
        // 每一对字符串的情况
        for(int i = 0;i < words.size()-1;i++){
            for(int j = i+1;j < words.size();j++){
                // 位运算判断两个字符串是否包含相同字符
                if((table[i] & table[j]) == 0){
                    int temp = words[i].length()*words[j].length();
                    if(temp > res){
                        res = temp;
                    }
                }
            }
        }
        return res;
    }
};

时间复杂度分析： 如果数组words的长度为n，平均每个字符串的长度为k，那么这种解法的时间复杂度是O（nk+n2），空间复杂度是O（n）。虽然两种解法的时间复杂度和空间复杂度是同一个量级的，但前面的解法在判断两个字符串是否包含相同的字符时，可能需要26次布尔运算，而新的解法只需要1次位运算，因此新的解法的时间效率更高。

结果：

补充内容

1. C++数组静态大小的数组不能使用变量来初始化，因为数组的大小必须在编译时就确定。即，这道题定义table时，如果写成bool table[1words.size()][26] = {false};会报错。
2. “|=”运算符：“a |= b”表示“a等于a与b的或”。
3. 在C++中，位运算符的优先级高于相等运算符。在if((table[i] & table[j]) == 0)中如果去掉(table[i] & table[j])的括号，会先进行table[j]) == 0的运算，导致结果错误。
4. 定义变量长度数组可以用vector。
   • vector的几种初始化及赋值方式
   • C++——二维vector初始化大小方法