最大单词长度乘积
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 106 ms, 内存: 16.4 MB
import java.util.*;
import java.util.stream.*;
/**
* 思路:
* 与Java的解法类似,但这里我们使用Stream来简化代码。
*/
public class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] masks = new int[n];
int[] lens = new int[n];
IntStream.range(0, n).forEach(i -> {
masks[i] = words[i].chars().reduce(0, (mask, c) -> mask | (1 << (c - 'a')));
lens[i] = words[i].length();
});
return IntStream.range(0, n).boxed()
.flatMap(i -> IntStream.range(i + 1, n).mapToObj(j -> new int[]{i, j}))
.filter(pair -> (masks[pair[0]] & masks[pair[1]]) == 0)
.mapToInt(pair -> lens[pair[0]] * lens[pair[1]])
.max().orElse(0);
}
}
解释
方法:
本题解采用了位运算和哈希表的方法来处理问题。首先,对于每个字符串,使用一个整数来表示其字符集,其中每个位的二进制表示是否包含从'a'到'z'的各个字符。这是通过遍历单词的每个字符,计算其相对于'a'的偏移,并将对应的位设置为1来完成的。然后,这个整数和单词的长度被存储在字典中,其中键是整数(字符集的位表示),值是对应的最长单词的长度。最后,对于字典中的每一对整数,如果两个整数的按位与为0(表示没有公共字符),则计算它们对应长度的乘积,并更新结果。
时间复杂度:
O(n * L + k^2)
空间复杂度:
O(k)
代码细节讲解
🦆
题解中提到用整数表示字符集,每个位的二进制表示字符是否存在。请问如何确保这种表示方式不会因为不同字符的组合而产生冲突?
▷🦆
为什么在填充字典时,只保留每种字符集对应的最长单词长度,而不是所有单词长度?
▷🦆
在比较字典中每对整数时,如果按位与结果为0,意味着两个字符串没有公共字符。但是,这种方法是否考虑了所有可能的字符集合组合?
▷