leetcode Maximum Product of Word Lengths

leetcode Maximum Product of Word Lengths

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.

Follow up:
Could you do better than O(n2), where n is the number of words?

题目地址: leetcode Maximum Product of Word Lengths

题意:给定一个字符串数组,求它们中,元素各不相同的字符串长度乘积最大值。

如样例1中,abcw 和 xtfn 成绩为4*4 =16 (元素互不相同) 而abcw 和 abcdef为0,因为有相同的元素

思路:

方法一

直接看看每个字符串都包括了哪个字符,然后一一枚举是否有交集:

  • 有交集,则乘积为0
  • 无交集,乘积为 words[i].length() * words[j].length()

于是写出如下代码

C++

方法二

其实因为全部都是小写的字母,用int 就可以存储每一位的信息。这就是位运算

  • elements[i] |= 1 << (words[i][j] – ‘a’);   //把words[i][j] 在26字母中的出现的次序变为1
  •  elements[i] & elements[j]    // 判断是否有交集只需要两个数 按位 与 (AND)运算即可

C++

Java

Python

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Maximum Product of Word Lengths
本文地址:https://www.hrwhisper.me/leetcode-maximum-product-of-word-lengths/

听说长得好看的已经打赏了

Leetcode , , , , . permalink.

3 thoughts on “leetcode Maximum Product of Word Lengths

Leave a Reply

Your email address will not be published. Required fields are marked *