Maximum product of leetcode/ word length

Code

package com.xcrj;

import java.util.HashMap;
import java.util.Map;

/** *  The finger of the sword  Offer II 005.  Maximum product of word length  *  Given an array of strings words, Please calculate when two strings  words[i]  and  words[j]  Does not contain the same characters , The maximum of the product of their lengths . Suppose that the string contains only English lowercase letters . If there is no pair of strings that do not contain the same characters , return  0. */
public class Solution5 {
    

    /** *  Brute force method , Traverse  */
    public int maxProduct1(String[] words) {
    
        int maxLen = 0;
        for (int i = 0; i < words.length; i++) {
    
            String wordi = words[i];
            // j=i: word0 and word1 It's been compared ,word1 and word0 Don't compare 
            for (int j = i; j < words.length; j++) {
    
                String wordj = words[j];
                if (!hasSameChar1(wordi, wordj)) {
    
                    maxLen = Math.max(maxLen, wordi.length() * wordj.length());
                }
            }
        }

        return maxLen;
    }

    /** * wordj.indexOf(c) *  Yes 1 The same characters return true */
    public boolean hasSameChar1(String wordi, String wordj) {
    
        for (char c : wordi.toCharArray()) {
    
            //  Only those who have 1 The same characters return true
            if (-1 != wordj.indexOf(c)) return true;
        }
        return false;
    }

    /** *  Letter   Array hash table statistics  */
    public int maxProduct2(String[] words) {
    
        int maxLen = 0;
        for (int i = 0; i < words.length; i++) {
    
            String wordi = words[i];
            // j=i: word0 and word1 It's been compared ,word1 and word0 Don't compare 
            for (int j = i; j < words.length; j++) {
    
                String wordj = words[j];
                if (!hasSameChar2(wordi, wordj)) {
    
                    maxLen = Math.max(maxLen, wordi.length() * wordj.length());
                }
            }
        }

        return maxLen;
    }

    /** *  Array hash table ： Hash different letters to different positions in the closed hash table  *  Hash function ：idx=c-'a' */
    public boolean hasSameChar2(String wordi, String wordj) {
    
        // 26 Letters ,26 A spatial hash table 
        int[] counts = new int[26];
        //  take wordi Put each letter in counts Different positions in the array 
        for (char c : wordi.toCharArray()) {
    
            int idx = c - 'a';
            counts[idx] = 1;
        }
        //  take wordj Put each letter in counts Different positions in the array 
        for (char c : wordj.toCharArray()) {
    
            int idx = c - 'a';
            // idx The hash position already has a value , Prove the existence of the same letter 
            if (1 == counts[idx]) {
    
                return true;
            }
        }

        return false;
    }


    /** *  Letter   Bit hash table statistics  */
    public int maxProduct3(String[] words) {
    
        int maxLen = 0;
        for (int i = 0; i < words.length; i++) {
    
            String wordi = words[i];
            // j=i: word0 and word1 It's been compared ,word1 and word0 Don't compare 
            for (int j = i; j < words.length; j++) {
    
                String wordj = words[j];
                if (!hasSameChar3(wordi, wordj)) {
    
                    maxLen = Math.max(maxLen, wordi.length() * wordj.length());
                }
            }
        }

        return maxLen;
    }

    /** *  Bit hash statistics  *  Hash function ：bitMask=1<<c-'a' */
    public boolean hasSameChar3(String wordi, String wordj) {
    
        //  structure 32bit Closed hash table 
        int bitMask1 = 0;
        int bitMask2 = 0;
        for (char c : wordi.toCharArray()) bitMask1 |= 1 << c - 'a';
        for (char c : wordj.toCharArray()) bitMask2 |= 1 << c - 'a';
        //  If there are no same characters & The result is 0;
        return 0 == (bitMask1 & bitMask2) ? false : true;
    }

    /** *  Get the bit hash representation of each word , Store in bitMasks[] in  */
    public int maxProduct4(String[] words) {
    
        //  Store the bit hash representation of each word 
        int[] bitMasks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
    
            String word = words[i];
            int bitMask = 0;
            for (char c : word.toCharArray()) bitMask |= 1 << c - 'a';
            bitMasks[i] = bitMask;
        }

        //  Look for words without the same bit 
        int maxLen = 0;
        for (int i = 0; i < bitMasks.length; i++) {
    
            int bitMaski = bitMasks[i];
            String wordi = words[i];
            for (int j = i; j < bitMasks.length; j++) {
    
                int bitMaskj = bitMasks[j];
                String wordj = words[j];
                if (0 == (bitMaski & bitMaskj)) {
    
                    maxLen = Math.max(maxLen, wordi.length() * wordj.length());
                }
            }
        }

        return maxLen;
    }

    /** * hashMap Statistical optimization maxProduct4 * Map<bitMask,Len> */
    public int maxProduct5(String[] words) {
    
        //  Store the bit hash representation of each word 
        Map<Integer, Integer> maskLenMap = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
    
            String word = words[i];
            int bitMask = 0;
            for (char c : word.toCharArray()) bitMask |= 1 << c - 'a';
            // ab aabb Of words bitMask Agreement , take aabb Maximum length of 
            maskLenMap.put(bitMask, Math.max(maskLenMap.getOrDefault(bitMask, 0), word.length()));
        }

        //  Find words that do not have the same characters 
        int maxLen = 0;
        for (int ki : maskLenMap.keySet()) {
    
            for (int kj : maskLenMap.keySet()) {
    
                //  Does not contain the same characters 
                if (0 == (ki & kj)) {
    
                    maxLen = Math.max(maxLen, maskLenMap.get(ki) * maskLenMap.get(kj));
                }
            }
        }

        return maxLen;
    }


    public static void main(String[] args) {
    
        Solution5 solution5 = new Solution5();
        System.out.println(solution5.maxProduct5(new String[]{
    "abcw", "baz", "foo", "bar", "fxyz", "abcdef"}));
    }
}

Reference resources

author ：tangweiqun
link ：https://leetcode.cn/problems/aseY1I/solution/jian-dan-yi-dong-javac-pythonjs-zui-da-d-ffga/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .