Maximum Product of Word Lengths

最新推荐文章于 2024-12-13 13:09:19 发布

假坏

最新推荐文章于 2024-12-13 13:09:19 发布

阅读量548

点赞数

分类专栏： LeetCode

本文链接：https://blog.csdn.net/scutwjh/article/details/50326177

版权

LeetCode 专栏收录该内容

31 篇文章

订阅专栏

本文介绍了一种算法，用于计算给定单词列表中不共享任何字母的两个单词的最大乘积长度。通过位运算技巧，实现高效计算。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n=words.size();
        vector<int> dict(n,0);
        for(int i=0;i<n;++i){
            for(char c:words[i]){
                dict[i]|=(1<<(c-'a'));
            }
        }
        
        int maxP=0;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(!(dict[i]&dict[j])){
                    int p=words[i].length()*words[j].length();
                    maxP=max(maxP,p);
                }
            }
        }
        return maxP;
    }
};