前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 318. Maximum Product of Word Lengths

LeetCode 318. Maximum Product of Word Lengths

作者头像
ShenduCC
发布2020-06-10 10:33:41
3420
发布2020-06-10 10:33:41
举报
文章被收录于专栏:算法修养

题目

这是一道字符串的题目,题目呢要求找到两个字符串没有重复的字符,且两者长度的乘积最大。暴力可以过。但是在比较字符串的时候可以用位运算,这样时间会大大缩短。

关于字符串,限制在只有小写字母的时候,位运算是可以运用起来,把一串字符用一个数字表示。两个字符串是否有重复,只需要位与一下就可以了

代码语言:javascript
复制
class Solution {
public:
    vector<int> nums;
    int maxProduct(vector<string>& words) {
        
        nums = vector<int>(words.size());
        for(int i=0;i<words.size();i++)
        {
            nums[i]=compute(words[i]);
        }
        
        int ans=0;
        for(int i=0;i<words.size();i++)
        {
            for(int j=i+1;j<words.size();j++)
            {
                if(!(nums[i]&nums[j]))
                {
                    if(ans < words[i].length()*words[j].length())
                        ans = words[i].length()*words[j].length();
                }
            }
        }
        return ans;
    }
    
    int compute(string s)
    {
        int bit = 0;
        for(int i=0;i<s.length();i++)
            bit |= (1<<(s[i]-'a'));
      
        return bit;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-06-08 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档