[algorithm] sword finger offer2 golang interview question 5: maximum product of word length

[ Algorithm ] The finger of the sword offer2 golang Interview questions 5： Maximum product of word length

subject 1:

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.

Example 1:

Input : words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
Output : 16
explain : These two words are “abcw”, “fxyz”. They do not contain the same characters , And the product of length is the largest .
Example 2:

Input : words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
Output : 4
explain : These two words are “ab”, “cd”.
Example 3:

Input : words = [“a”,“aa”,“aaa”,“aaaa”]
Output : 0
explain : There are no such two words .

Tips ：

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] Only lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/aseY1I
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas 1:

The number of letters is only 26 individual , We can use one int 32 To record whether the word contains the letter

such as
“ac” 0101
ac: Last 1 On behalf of a There is , Next to last 0 representative b non-existent
“bd” 1010

ac Binary system & bd If the binary of is 0, Prove different , On the contrary, they are the same

• take word Convert to binary time complexity O(n*k)
• Use & The operation finds no duplicate numbers word Calculation length refresh length time complexity O(n2)

Code

func maxProduct(words []string) int {
    
    // Ideas : 
    // *  take word Convert to binary time complexity  O(n*k)
    // *  Use  &  The operation finds no duplicate numbers  word  Calculation length refresh length time complexity  O(n2)
    
    // Processing parameters 
    if len(words) < 2 {
    
        return 0
    }

    // take word Convert to binary time complexity  O(n*k)
    nums := make([]int,len(words))
    for i:=0;i<len(words);i++ {
    
        for j:=0;j<len(words[i]);j++{
    
            nums[i] |= (1<<(words[i][j] - 'a'))
        }
    }

    // Use  &  The operation finds no duplicate numbers  word  Calculation length refresh length time complexity  O(n2)
    max := 0
    for i:=0;i<len(words);i++ {
    
        for j:=i + 1;j<len(words);j++{
    
            if nums[i] & nums[j] == 0 {
    
                tempMax := len(words[i]) * len(words[j])
                if tempMax > max {
    
                    max = tempMax
                }
            }
        } 
    } 
    return max
}

test