318. Maximum Product of Word Lengths - YRB - 博客园
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.
链接： https://leetcode.com/problems/maximum-product-of-word-lengths/
题解：
给定一个String array，求出不含相同字符的两个单词长度乘积的最大值。
我们可以把这道题目分为几个步骤。
- 双重循环遍历Words
- 先把words[i]和words[j]放入一个<String, Set<Character>>的HashMap里
- 比较两者是否有重复， 假如没有重复，我们可以尝试更新max， 否则continue
- 最后返回max
这里题目给出单词只包含小写字母，所以我们还可以进一步优化空间复杂度。 另外，预先对数组按长度进行排序的话应该可以剪枝掉不少计算。 留给二刷了。
Java:
Read full article from 318. Maximum Product of Word Lengths - YRB - 博客园
No comments:
Post a Comment