题目描述

单词长度的最大乘积
示例 1:

  1. 输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
  2. 输出: 16 
  3. 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。

示例 2:

  1. 输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
  2. 输出: 4 
  3. 解释: 这两个单词为 "ab", "cd"。

示例 3:

  1. 输入: words = ["a","aa","aaa","aaaa"]
  2. 输出: 0 
  3. 解释: 不存在这样的两个单词。

提示：

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000

  • words[i] 仅包含小写字母

    解题思路

    左思右想只能想到暴力解法，用HashSet去重，判交集。
    image.png
    效率太低了。
    看题解
    二进制，字符串
    这思路！
    image.png
    因为字符串中的字符每个都是26个字母中的一个，而int是32位的，那就可以用int的位的0/1表示是否存在该字母。先一次遍历将字符串用按位或运算转为int数。 用按位与运算判断两个数是否有交集。顺序遍历求Max

    实现代码

    1. public int maxProduct(String[] words) {
    2. int[] wordsArray = new int[words.length];
    3. //int数转换
    4. for (int i = 0, end = words.length; i < end; i++) {
    5.     for (char letter : words[i].toCharArray()) {
    6.         wordsArray[i] |= (1 << (letter - 'a'));
    7.     }
    8. }
    10. int product = 0;
    11. for (int i = 0, end = words.length; i < end; i++) {
    12.     for (int j = i + 1; j < end; j++) {
    13.         if ((wordsArray[i] & wordsArray[j]) == 0) {
    14.       product = Math.max(product, words[i].length() * words[j].length());
    15.     }
    16.     }
    17. }
    18. return product;
    19. }
    20. 作者：huaLuoYueQue
    21. 链接：https://leetcode-cn.com/problems/aseY1I/solution/hua-luo-yue-que-bei-li-yong-che-di-de-er-loai/
    22. 来源：力扣（LeetCode）
    23. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    时间及空间复杂度分析

    真正耗时的操作在于如何判断两个字符串存在，用二进制算是最高效率的方式，时间复杂度O(n2)
    空间复杂度只需要O(n)
    image.png

    拓展思路