【LeetCode】单词长度的最大乘积 Java 题解

2022 年 5 月 31 日
本文字数：1027 字
阅读完需：约 3 分钟

题目描述

给定一个字符串数组 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 解释: 不存在这样的两个单词。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/aseY1I著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串处理题目。我们拆解成两个小问题，一个是判断两个字符串是否包含相同的字符，当不包含相同的字符时候，我们去计算他们的乘积。
具体来说，判断两个字符串是否包含相同的字符，我们可以使用 s.indexOf() 函数。indexOf() 的实现是每次都遍历字符串，然后来返回结果。时间复杂度较高。针对重复计算，可以采用计数的方式来判断是否含有相同的字符，具体来说，就是先统计 word1 中所有的字符和字符的出现次数，然后判断 word2 是否包含相同的字符。具体实现代码如下，供参考。

通过代码

class Solution {    public int maxProduct(String[] words) {        int ans = 0;        for (int i = 0; i < words.length; i++) {            String word1 = words[i];            for (int j = i + 1; j < words.length; j++) {                String word2 = words[j];                // 每个单词的 bitMask 会重复计算很多次                if (!hasSameChar(word1, word2)) {                    ans = Math.max(ans, word1.length() * word2.length());                }            }        }        return ans;    }
    private boolean hasSameChar(String word1, String word2) {        int[] count = new int[26];        for (char c : word1.toCharArray()){             count[c - 'a'] = 1;        }        for (char c : word2.toCharArray()) {            if (count[c - 'a'] == 1) return true;        }        return false;    }}