🌕🌗 318. 最大单词长度乘积

难度: 🌕🌗

问题描述

---

解法 1

class Solution {
    public int maxProduct(String[] words) {
        // 思路：
        // 位运算
        // 直接想法就是依次遍历每个单词，判断和其他单词是否有公共字母，若不存在，更新 res
        // 如何判断 cur & 其他单词 是否有公共字母？
        // 由于只含小写字母，最直接方法是 cur 映射到一个 boolean[26] 中，其他单词也映射到一个 boolean[26] 中，取交集
        // 但是这样复杂度比较高，我们只需要判断对应 下标 是否存在，也无需管对应下标处的字符次数
        // 因此可以将 boolean[26] 折算成一个 int 值，通过 1<< index 得到 int

        int len = words.length;
        int[] array = new int[len]; // 存放不同下标单词 映射的 int 值
        for(int i = 0; i < len; i ++) {
            String cur = words[i];
            int val = 0;
            // 遍历 当前单词 的每个字符，进行映射
            for(int j = 0; j < cur.length(); j ++) {
                int left = cur.charAt(j) - 'a'; // 需要左移的位数
                val |= (1 << left);
            }
            array[i] = val;
        }

        int res = 0;
        for(int i = 0; i < len - 1; i ++) {
            for(int j = i + 1; j < len; j ++) {
                if((array[i] & array[j]) == 0) {
                    // 说明 [0, 25] 位中没有同时出现的 1，即没有公共字母，更新 res
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
}

---

输出 1

---

解法 - 优化

class Solution {
    public int maxProduct(String[] words) {
        // 思路：
        // 由于 {meet, met, memet} 这类单词最终映射的 val 均相同，因此可以通过 HashMap 存储 val
        // 遍历的时候，也只遍历 map 集合，而非 word[] 
        // 当 这类单词 经常出现时，针对这种用例，可以达到优化效果
        int len = words.length;
        HashMap<Integer, Integer> map = new HashMap<>(); // val - val 对应的最长单词长度
        
        for(String cur: words) {
            int size = cur.length();
            int val = 0;
            for(int j = 0; j < size; j ++) {
                int left = cur.charAt(j) - 'a';
                val |= (1 << left);
            }
            if(!map.containsKey(val)) {
                map.put(val, size);
            } else {
                int preLen = map.get(val);
                if(size > preLen) {
                    map.put(val, size); // 更新 val 对应的最长单词长度
                }
            }
        }

        // 遍历 map
        int res = 0;
        for(int a: map.keySet()) {
            for(int b: map.keySet()) {
                // 当 a == b 时，a & b 必 != 0，因此无需特殊情况特判
                if((a & b) == 0) {
                    res = Math.max(res, map.get(a) * map.get(b));
                }
            }
        }
        return res;
    }
}

---

输出