LeetCode题练习与总结：最大单词长度乘积--318

一、题目描述

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 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] 仅包含小写字母

二、解题思路

1. 首先计算每个单词的长度，并存储在一个数组中。
2. 使用一个布尔数组来表示每个单词中字母的存在情况。由于单词只包含小写字母，可以使用一个长度为26的布尔数组来表示每个字母是否存在。
3. 遍历单词数组，对于每一对单词，检查它们的字母存在情况数组是否有交集。如果没有交集，则计算它们的长度乘积，并更新最大乘积。
4. 返回最大乘积。

三、具体代码

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] lengths = new int[n];
        int[][] letters = new int[n][26];

        // 计算每个单词的长度，并记录每个单词的字母存在情况
        for (int i = 0; i < n; i++) {
            lengths[i] = words[i].length();
            for (char c : words[i].toCharArray()) {
                letters[i][c - 'a'] = 1;
            }
        }

        int maxProduct = 0;
        // 遍历每一对单词，检查它们的字母存在情况是否有交集
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!hasCommonLetters(letters[i], letters[j])) {
                    maxProduct = Math.max(maxProduct, lengths[i] * lengths[j]);
                }
            }
        }

        return maxProduct;
    }

    // 检查两个单词是否有公共字母
    private boolean hasCommonLetters(int[] letters1, int[] letters2) {
        for (int i = 0; i < 26; i++) {
            if (letters1[i] == 1 && letters2[i] == 1) {
                return true;
            }
        }
        return false;
    }
}

在这个代码中，hasCommonLetters 方法用于检查两个单词是否有公共字母。如果有，则返回 true，否则返回 false。在 maxProduct 方法中，我们使用双重循环来遍历每一对单词，并使用 hasCommonLetters 方法来检查它们是否有公共字母。如果没有公共字母，我们计算它们的长度乘积，并更新最大乘积。最后返回最大乘积。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 计算每个单词的长度并记录字母存在情况：

  • 对于每个单词，我们需要遍历它的每个字符来记录字母的存在情况。假设单词的平均长度为 L，那么对于每个单词，这一步的时间复杂度为 O(L)。
  • 由于我们需要对 n 个单词都执行这个操作，所以这一步的总时间复杂度为 O(n * L)。

• 检查每一对单词是否有公共字母并计算最大乘积：

  • 我们使用了两层循环来遍历每一对单词，第一层循环的时间复杂度为 O(n)，第二层循环的时间复杂度为 O(n - i)（其中 i 是外层循环的索引），因此两层循环的总时间复杂度为 O(n^2)。
  • 对于每一对单词，我们需要检查它们的字母存在情况是否有交集，这个操作的时间复杂度为 O(26)，即 O(1)，因为无论单词的长度如何，我们总是检查26个字母。

综合以上两步，总的时间复杂度为 O(n * L + n^2)。由于 L 是单词的平均长度，而 n 是单词的数量，通常情况下 L 不会比 n 大很多，所以我们可以近似地将时间复杂度简化为 O(n^2)。

2. 空间复杂度

• 记录每个单词长度的数组 lengths：

  • 这个数组的大小为 n，所以空间复杂度为 O(n)。

• 记录每个单词字母存在情况的二维数组 letters：

  • 这个数组的大小为 n * 26，所以空间复杂度为 O(n)。

• 辅助变量 maxProduct 和循环索引 i, j：

  • 这些变量占用常数空间，空间复杂度为 O(1)。

综合以上空间占用，总的空间复杂度为 O(n)。

五、总结知识点

• 数组的声明与初始化：

  • 声明并初始化一个一维数组 lengths 来存储每个单词的长度。
  • 声明并初始化一个二维数组 letters 来存储每个单词的字母存在情况。

• 字符与整数的转换：

  • 使用字符变量 c 与字符 ‘a’ 进行减法操作，将字符转换为对应的整数索引，用于二维数组 letters 的访问。

• 循环结构：

  • 使用 for 循环来遍历数组 words 中的每个单词。
  • 使用嵌套的 for 循环来遍历每一对单词，以检查它们是否有公共字母。

• 字符串处理：

  • 使用 String.toCharArray() 方法将字符串转换为字符数组，以便遍历每个字符。

• 逻辑判断：

  • 在 hasCommonLetters 方法中使用 if 语句来检查两个单词是否有公共字母。

• 位运算：

  • 在 letters 数组中使用 1 表示某个字母存在于单词中，这是位运算的一种简单应用。

• 数学运算：

  • 使用 Math.max() 方法来更新最大乘积 maxProduct。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。