leetcode 318. Maximum Product of Word Lengths | 318. 最大单词长度乘积

你的名字 2022-10-19 13:59 29阅读 0赞

## 题目 ##

[https://leetcode.com/problems/maximum-product-of-word-lengths/][https_leetcode.com_problems_maximum-product-of-word-lengths]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

中规中矩的题目，中规中矩的思路，不像是一个 medium 题。直接上草稿。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int maxProduct(String[] words) { 
            boolean[][] a = new boolean[words.length][26];
            for (int i = 0; i < words.length; i++) { 
                for (int j = 0; j < words[i].length(); j++) { 
                    a[i][words[i].charAt(j) - 'a'] = true;
                }
            }
            int maxProduct = 0;
            for (int i = 0; i < words.length; i++) { 
                for (int j = i + 1; j < words.length; j++) { 
                    // if (words[i].length() * words[j].length() < maxProduct) continue; // 剪枝（优化效果不明显）
                    int k;
                    for (k = 0; k < words[i].length(); k++) { 
                        if (a[j][words[i].charAt(k) - 'a']) break;
                    }
                    if (k == words[i].length()) maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
                }
            }
            return maxProduct;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_maximum-product-of-word-lengths]: https://leetcode.com/problems/maximum-product-of-word-lengths/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/0a80aca709434843a59ec546323125e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221004/30053ac306364bc8896b226daa0434b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221004/67ff93de26cf423aadbde7a1fbd30023.png