本文共 882 字，大约阅读时间需要 2 分钟。
题目链接：
题目描述：
给定多个字母串，求其中任意两个字母串的长度乘积的最大值，且这两个字母串不能含有相同字母。 输入: ["abcw","baz","foo","bar","xtfn","abcdef"]输出: 16
输入: ["a","ab","abc","d","cd","bcd","abcd"]输出: 4
题目分析：
可以为每个字母串建立一个长度为 26 的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的按位与不为 0 。同时，我们可以建立一个哈希表来存储字母串（在数组的位置）到二进制数字的映射关系，方便查找调用 代码： int maxProduct(vector &words){ unordered_map hash; int ans=0; for(const string &word:words) { int mask=0,size=word.size(); for(const char &c:word)//用 c来接收word里面每一个字符 { mask|=1<<(c-'a');//创建位掩码:遍历单词的每个字母，计算该字母在掩码中的位置 n = (int)ch - (int)'a'，然后创建一个第 n 位为 1 的掩码 n_th_bit = 1 << n //然后通过或操作将该码合并到位掩码中 bitmask |= n_th_bit } hash[mask]=max(hash[mask],size); for(const auto&[h_mask,h_len]:hash)//计算两个不同字符串的最大长度的乘积 { if(!(mask&h_mask))//若为0则含有重复字符 { ans=max(ans,size*h_len); } } } return ans; }
转载地址：http://ualx.baihongyu.com/