LeetCode-318. 最大单词长度乘积

Dear 丶 2024-03-22 11:52 54阅读 0赞

#### 目录 ####

*   *  题目思路
     *  代码实现

题目来源  
[318. 最大单词长度乘积][318.]

### 题目思路 ###

我们可以使用一个 int 来代指某个 word\[i\]：低 26 来代指字母 a-z 是否出现过。  
然后对每个「字符对」所对应的两个 int 值执行 & 操作（若两字符无重复字符，则结果为 0），并得出最终答案。

![在这里插入图片描述][d60b3fe941e945b9bd3b8f833bd6655e.png]

### 代码实现 ###

class Solution {
        
        public int maxProduct(String[] words) {
        
            //如果数组为空，直接返回0
            if(words.length == 0 || words == null){
        
                return 0;
            }
            //定义一个数组，用来存储字符串的值
            int[] arr = new int[words.length];
            //定义一个索引值，用来递增
            int index = 0;
            //遍历数组字符串，得到单个字符串
            for(String str : words){
        
                //定义一个ans结果，存入arr数组中
                int ans = 0;
                //遍历字符串中的每个字符
                for(int i = 0;i<str.length();i++){
        
                    //得到当前索引的字符
                    char c = str.charAt(i);
                    //向左移(c-'a')位，然后使用|
                    ans |= 1<<(c-'a');
                }
                //把结果ans结果写入到arr数组中
                arr[index++] = ans;
            }
            //定义最终的结果
            int res = 0;
            //两个for循环，依次遍历求最长的单词数量
            for(int i = 0;i<words.length;i++){
        
                for(int j = 0;j<i;j++){
        
                    //&如果为0，说明这个单词不相同
                    if((arr[i] & arr[j]) == 0){
        
                        res = Math.max(res,words[i].length() * words[j].length());
                    }
                }
            }
            return res;
        }
    }

![在这里插入图片描述][78aca9f402f04cd8a8788405d6d7e561.png]

[318.]: https://leetcode.cn/problems/maximum-product-of-word-lengths/
[d60b3fe941e945b9bd3b8f833bd6655e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/2af4cbeba58b40d69f3423ba9ffbd7eb.png
[78aca9f402f04cd8a8788405d6d7e561.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b8ef2723f7a7487ab37e6a7a8f0f1d61.png