力扣刷题笔记【位运算】 → 318 最大单词长度乘积

发表于

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战

题目

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例

1
2
3
arduino复制代码输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。
1
2
3
arduino复制代码输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。
1
2
3
less复制代码输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

提示

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i] 仅包含小写字母

解题思路

位运算

暴力的解法是两层遍历，再分别判断每一个字符串是否与其它字符串有公共字母，这样的时间复杂度太高了，会导致结果超时。

在暴力法中，我们每一次都需要计算每个字符串里面的元素，那么我们可以找一个变量，将该次计算结果进行保存，后续需要用到的时候，直接拿来使用就好来，这样就不要进行重复的计算操作。

同时，由于words数组仅包含小写字母，仅有26位，那么我们可以利用二进制的特性，通过与运算来快速得出两个字符串是否有公共字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
java复制代码class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        // 定义数组，保存每一个字符串的字母
        int[] arr = new int[n];
        for(int i = 0; i < n; ++i){
            int tmp = 0;
            // 遍历字符串
            for(char w : words[i].toCharArray()){
                // 将对应元素标记为 1
                tmp |= (1 << (w - 'a'));
            }
            // 赋值
            arr[i] = tmp;
        }

        // 最大值
        int max = 0;
        
        // 将字符串与数组中其它字符串进行对比
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                // 如果没有公共字母，则更新最大值
                if((arr[i] & arr[j]) == 0){
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        
        // 返回结果
        return max;
    }
}

复杂度分析

  • 时间复杂度：O(N2)O(N^2)O(N2)
  • 空间复杂度：O(N)O(N)O(N)

最后

文章有写的不好的地方，请大佬们不吝赐教，错误是最能让人成长的，愿我与大佬间的距离逐渐缩短！

如果觉得文章对你有帮助，请 点赞、收藏、关注、评论 一键四连支持，你的支持就是我创作最大的动力！！！

题目出处: leetcode-cn.com/problems/ma…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%