【每日一道剑指 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(N3)，空间复杂度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+N2)，空间复杂度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; } };
