leetcode
leetcode 2901 ~ 2950
最大单词长度乘积

最大单词长度乘积

难度:

标签:

题目描述

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)

代码细节讲解

🦆
题解中提到用整数表示字符集,每个位的二进制表示字符是否存在。请问如何确保这种表示方式不会因为不同字符的组合而产生冲突?
在本题解中,使用一个整数的每一位来表示一个字符是否存在,总共有26个英文字母,因此至少需要26位来表示所有可能的字符。由于整数类型通常至少有32位,完全足够表示所有英文小写字母。这种方法中,每个位独立代表一个字符,不同字符的组合不会影响其他位,因此不存在不同字符组合会导致表示冲突的问题。例如,字符'a'对应整数的第0位,字符'b'对应第1位,即使在不同单词中字符的组合不同,它们在整数中的表示也不会互相影响。
🦆
为什么在填充字典时,只保留每种字符集对应的最长单词长度,而不是所有单词长度?
在解决这个问题的目标是找到没有共同字符的两个单词,它们长度的乘积最大。如果两个单词具有相同的字符集,那么它们之间无法形成有效的乘积对(因为它们的按位与不为0)。因此,对于具有相同字符集的单词,只保留最长的单词可以简化问题的复杂度,因为只有最长的单词才可能与其他字符集的单词组合形成最大的乘积。存储所有单词长度将增加不必要的空间和计算复杂度,而不会影响最终结果。
🦆
在比较字典中每对整数时,如果按位与结果为0,意味着两个字符串没有公共字符。但是,这种方法是否考虑了所有可能的字符集合组合?
是的,这种方法确实考虑了所有可能的字符集合组合。通过将每个单词的字符集转换为整数表示,并将这些整数作为字典的键,我们可以确保每个独特的字符集都被考虑到。在比较过程中,我们检查所有可能的整数对,如果两个整数的按位与为0,意味着这两个整数代表的字符集没有交集,即对应的单词没有公共字符。这样的方法系统地覆盖了所有独特字符集的组合,确保不遗漏任何一个可能的乘积对。

相关问题