[leetcode] 318. Maximum Product of Word Lengths

[leetcode] 318. Maximum Product of Word Lengths

Description

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:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]Output: 16 Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: ["a","ab","abc","d","cd","bcd","abcd"]Output: 4 Explanation: The two words can be "ab", "cd".

Example 3:

Input: ["a","aa","aaa","aaaa"]Output: 0 Explanation: No such pair of words.

分析

题目的意思是：给定一个单词数组，找到两个单词长度的最大的积，其中两个单词的字符相互不包含。

因为题目中说都是小写字母，那么只有26位，一个整型数int有32位，我们可以用后26位来对应26个字母，若为1，说明该对应位置的字母出现过，那么每个单词的都可由一个int数字表示，两个单词没有共同字母的条件是这两个int数相与为0。

代码

class Solution {public: int maxProduct(vector& words) { int res=0; vector mask(words.size(),0); for(int i=0;i

参考文献

​​[LeetCode] Maximum Product of Word Lengths 单词长度的最大积​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。