【每日一道剑指 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 <= 10001 <= words[i].length <= 1000words[i] 仅包含小写字母

解题思路

暴力解法

时间复杂度O(N³)，空间复杂度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²)，空间复杂度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  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中每个字符串中的单个字符是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;    }};

💫点击直接资料领取💫

❤️关注苏州程序大白公众号❤️

👇 👇👇