318.最大单词长度乘积

链接：318.最大单词长度乘积
难度：Medium
标签：位运算、数组、字符串
简介：给定一个字符串数组  words，找到  length(word[i]) * length(word[j])  的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

题解 1 - python

• 编辑时间：2023-11-06
• 执行用时：844ms
• 内存消耗：18.57MB
• 编程语言：python
• 解法介绍：哈希存储。

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        m = { word: reduce(lambda n, c: n | 1 << ord(c), word, 0) for word in words}
        return max(len(word1) * len(word2) if m[word1] & m[word2] == 0 else 0 for word1 in words for word2 in words)

题解 2 - typescript

• 编辑时间：2021-07-24
• 执行用时：140ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：利用二进制从储存每个单词的哈希值。

function maxProduct(words: string[]): number {
  const map: Record<string, number> = {};
  for (const word of words) {
    let v = 0;
    for (let i = 0, l = word.length; i < l; i++) {
      v |= 1 << word.codePointAt(i)!;
    }
    map[word] = v;
  }
  let ans = 0;
  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if ((map[words[i]] & map[words[j]]) === 0) {
        ans = Math.max(ans, words[i].length * words[j].length);
      }
    }
  }
  return ans;
}

题解 3 - c

• 编辑时间：2021-11-17
• 执行用时：32ms
• 内存消耗：7.6MB
• 编程语言：c
• 解法介绍：位运算统计每个词出现的字母。

void formatWord(char *word, int *bit, int *size){
    for(int i = 0; word[i] != '\0'; i++){
        *bit |= 1 << (word[i] - 'a');
        *size += 1;
    }
}
int maxProduct(char ** words, int wordsSize){
    int word_bit[wordsSize], word_size[wordsSize];
    for (int i = 0; i < wordsSize; i++) word_bit[i] = 0, word_size[i] = 0;
    for (int i = 0; i < wordsSize; i++) {
        char *word = words[i];
        formatWord(word, &word_bit[i], &word_size[i]);
    }
    int ans = 0;
    for (int i = 0; i < wordsSize; i++) {
        for (int j = 0; j < wordsSize; j++) {
            if (word_bit[i] & word_bit[j]) continue;
            int len = word_size[i] * word_size[j];
            ans = ans < len ? len : ans;
        }
    }
    return ans;
}

题解 4 - cpp

• 编辑时间：2021-12-24
• 执行用时：364ms
• 内存消耗：20.4MB
• 编程语言：cpp
• 解法介绍：用二进制存储每个字符串存在的字符，两个字符串值与运算为 0 说明无重复。

class Solution {
   public:
    int s2i(string str) {
        int ans = 0;
        for (auto &ch : str) ans |= 1 << (ch - 'a');
        return ans;
    }
    int maxProduct(vector<string> &words) {
        unordered_map<string, int> mmap;
        for (auto &word : words) mmap[word] = s2i(word);
        int ans = 0;
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (mmap[words[i]] & mmap[words[j]]) continue;
                ans = max(ans, (int)(words[i].size() * words[j].size()));
            }
        }
        return ans;
    }
};

题解 5 - typescript

• 编辑时间：2021-11-17
• 执行用时：96ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：位运算统计每个词出现的字母。

function maxProduct(words: string[]): number {
  const n = words.length;
  const bit_words = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    const word = words[i];
    for (let pos = 0, l = word.length; pos < l; pos++) {
      bit_words[i] |= 1 << (word.codePointAt(pos)! - 97);
    }
  }
  let ans = 0;
  for (let i = 0; i < n; i++) {
    const len1 = words[i].length;
    const bit1 = bit_words[i];
    for (let j = i + 1; j < n; j++) {
      const len2 = words[j].length;
      const bit2 = bit_words[j];
      if (bit1 & bit2) continue;
      ans = Math.max(ans, len1 * len2);
    }
  }
  return ans;
}