leetcode318. Maximum Product of Word Lengths

Moxmi 发布于2019-08-15 14:43 / 2597人阅读

摘要：将低位的二进制数分别对应字母，从而用二进制数实现一个简单的。因此单词对应的二进制数为那么比较两个单词是否有重复的字母只需要将二者的二进制形式进行操作即可。

题目要求

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. 
You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

有一个字符串数组，从该字符串数组中找到两个字符串，要求满足这两个字符串之间没有相同的字母，同时它们的长度的乘积最大。

思路和代码

这道题的重点在于如何优化字符串的比较。直观的来说，我们无法避开复杂度为O(n^2)的循环因为必须进行两两比较才能识别出最大的乘积。但是我们可以优化字符串的比较。

既然只需要知道两个字符串是否有相同的字母，那么我们可以采用一种数据结构将每个单词所有的字母记录下来。这里采用的是二进制数的形式。我们知道字母的数量不会超过26个，因此我们使用32位的整数来存储。将低26位的二进制数分别对应字母a-z，从而用二进制数实现一个简单的map。

因此单词ae对应的二进制数为00000000 00000000 00000000 00010001

那么比较两个单词是否有重复的字母只需要将二者的二进制形式进行&操作即可。如果没有重复字母，则结果应该为0.

public int maxProduct(String[] words) {
        int length = words.length;
        int[] wordToInt = new int[length];
        for(int i = 0 ; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Lengths Maximum Leetcod Product

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68775.html

Maximum Product of Word Lengths

摘要：题目链接除了用先处理之外，还可以用保存所有不含某个字母的，这么写。 Maximum Product of Word Lengths 题目链接：https://leetcode.com/problems... public class Solution { public int maxProduct(String[] words) { // bit array t...

妤锋シ 2019-08-14 17:24 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] 628. Maximum Product of Three Numbers

Problem Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1:Input: [1,2,3]Output: 6Example 2:Input: [1,2,3,4]Output: 24Note:The length of the ...

jindong 2019-08-16 13:39 评论0 收藏0
leetcode 628 Maximum Product of Three Numbers

摘要：题目详情输入一个大小大于等于三的数组，给出其中任意三个数乘积中的最大乘积想法这道题最主要的是要考虑正负数的情况。如果全都是正数相乘比较大，就取三个最大值相乘即可。题目详情 Given an integer array, find three numbers whose product is maximum and output the maximum product.输入一个大小大于...

CoreDump 2019-08-15 13:57 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0