## 题目描述 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。 ### 输入输出 #### 示例1 ``` 输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"] 输出: 16 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。 ``` #### 示例2 ``` 输入: words = ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4 解释: 这两个单词为 "ab", "cd"。 ``` #### 示例3 ``` 输入: words = ["a","aa","aaa","aaaa"] 输出: 0 解释: 不存在这样的两个单词。 ``` #### 提示 - 2 <= words.length <= 1000 - 1 <= words[i].length <= 1000 - words[i] 仅包含小写字母 ### 题目解答 #### 解题思路 题目的关键点，就在于判断两个字符串是否有包含相同字符。两两比较肯定涉及一个二重循环，但是比较的时间是一个关键点。 **位运算的比较方式** 通过int类型记录每个单词字母出现情况，将26个字母在int类型的对应位置为1。通过对两个整形int进行**与运算**如果为0的话，则这两个单词没有相同字符。 **计算复杂度** 设一共单词数量N，每个单词平均长度M。 时间复杂度：记录每个单词的字母出现情况复杂度$$O(N \times M)$$, 两两比较复杂度$$O(N^2)$$, 整体复杂度还是$$O(N \times M + N^2)$$，这样一个平方级别。 空间复杂度：需要增加一个长度N的int类型数组，记录单词字母出现情况，空间复杂度$$O(N)$$ #### 代码实现 ```java public int maxProduct(String[] words) { int max = 0; int[] record = new int[words.length]; for(int i=0;i<words.length;i++){ for(int j=0;j<words[i].length();j++){ record[i] |= 1 << (words[i].charAt(j) - 'a'); } } for(int i=0;i<words.length;i++){ for(int j=i+1;j<words.length;j++){ // 不含相同字符 if((record[i] & record[j])==0){ int len = words[i].length() * words[j].length(); if(len > max) max = len; } } } return max; } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复