@[TOC](【每日一道剑指 Offer】 算法·每日一题（详解+多解）-- day4)

✨博主介绍

🌊 作者主页：苏州程序大白

🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司

💬如果文章对你有帮助，欢迎关注、点赞、收藏

💅 有任何问题欢迎私信，看到会及时回复
💅关注苏州程序大白，分享粉丝福利

单词长度的最大乘积

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

示例 1:
输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。

示例 2:
输入: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
输出: 4
解释: 这两个单词为 “ab”, “cd”。

示例 3:
输入: words = [“a”,“aa”,“aaa”,“aaaa”]
输出: 0
解释: 不存在这样的两个单词。

提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

解题思路

暴力解法

时间复杂度O(N^3^)，空间复杂度O(N)

class Solution {
    
    public int maxProduct(String[] words) {
        int n = words.length;
        int max = 0;
        
        //暴力遍历
        for (int i=0; i<n; i++){
            for (int j=i+1; j<n; j++){
                if (isRe(words[i], words[j])) continue;
                max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        return max;
    }
    //使用HashSet判断两个字符串中是否存在相同的字符
    public boolean isRe(String one, String two){
        char[] charOne = one.toCharArray();
        char[] charTwo = two.toCharArray();

        HashSet<Character> set = new HashSet();
		//存入第一个字符串
        for (int i=0; i<charOne.length; i++) set.add(charOne[i]);
        //判断第二个字符串是否有重复字符
        for (int i=0; i<charTwo.length; i++)
            if (set.contains(charTwo[i])) 
                return true;

        return false;
    }
}

位运算

解法：

因为只有26个小写字符，所以直接使用一个int存储字符出现的情况，然后枚举最大乘积使用二进制低26位表示字母a~z。若出现过用1表示，否则用0。

用数组mask记录每个字母的位掩码1 << (ch - ‘a’)：将低26位中ch - 'a’的位置置为1当且仅当 masks[i] & masks[j] = 0时第 i 个单词和第 j 个单词没有公共字母时间复杂度O(L+N^2^)，空间复杂度O(N)。

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int max = 0;
        int[] mask = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (char ch : words[i].toCharArray()) {
                mask[i] |= 1 << (ch - 'a');
            }
        }
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((mask[i] & mask[j]) == 0) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
    }
}

二进制,字符串

二进制,字符串用26位二进制数表示,int有32位，只用到26位就够了
例：字符串中有a,那么32-26=6，flags[i]中的第7位为1，反之为0，有b的话，第8位为0…

class Solution {
public:
    int maxProduct(vector<string>& words) {
        //int数组用来使用二进制形式表示字符出串
        //vector<int>  flags; //未赋初值（做初始化），出问题
        vector<int> flags(words.size(),0); //数组做初始化
        //int flags[words.size()]; //未做初始化，会出问题，分配的内存中可能有脏数据

        for(int i=0;i< words.size();i++){
            for(char c: words[i]){   //使用范围for语句，这样是可以用的，开始出问题是因为数组为做初始化导致的
            //for(int j=0;j<words[i].length();j++){   
                  // flags[i] |=1<<(words[i][j]-'a');   //words[i][j]这样操作vector<string>中每个字符串中的单个字符是ok的
                  flags[i] |=1<<(c-'a');
            }
        }

        int result=0;
        for(int i=0;i<words.size();i++){
            for(int j=i+1;j<words.size();j++){
                if((flags[i]&flags[j])==0){
                    int prod = words[i].length() * words[j].length();
                    result =  max(result,prod);
                }
            }
        }

        return result;

    }
};

💫点击直接资料领取💫