Question

318. 最大单词长度乘积

English Version

题目描述

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

 

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

 

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

解法

方法一：位运算

题目需要我们找到两个没有公共字母的字符串，使得它们的长度乘积最大。我们可以将每个字符串用一个二进制数 $mask[i]$ 表示，这个二进制数的每一位表示字符串中是否含有某个字母。如果两个字符串没有公共字母，那么这两个字符串对应的二进制数的按位与的结果为 $0$，即 $mask[i] \& mask[j] = 0$。

我们遍历每个字符串，对于当前遍历到的字符串 $words[i]$，我们先算出对应的二进制数 $mask[i]$，然后再遍历 $j \in [0, i)$ 的所有字符串 $words[j]$，检查 $mask[i] \& mask[j] = 0$ 是否成立，如果成立就更新答案为 $\max(ans, |words[i]| \times |words[j]|)$。

遍历结束后，返回答案即可。

时间复杂度 $O(n^2 + L)$，空间复杂度 $O(n)$。其中 $n$ 是字符串数组 $words$ 的长度，而 $L$ 是字符串数组所有字符串的长度之和。

class Solution:
  def maxProduct(self, words: List[str]) -> int:
    mask = [0] * len(words)
    ans = 0
    for i, s in enumerate(words):
      for c in s:
        mask[i] |= 1 << (ord(c) - ord("a"))
      for j, t in enumerate(words[:i]):
        if (mask[i] & mask[j]) == 0:
          ans = max(ans, len(s) * len(t))
    return ans

class Solution {
  public int maxProduct(String[] words) {
    int n = words.length;
    int[] mask = new int[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (char c : words[i].toCharArray()) {
        mask[i] |= 1 << (c - 'a');
      }
      for (int j = 0; j < i; ++j) {
        if ((mask[i] & mask[j]) == 0) {
          ans = Math.max(ans, words[i].length() * words[j].length());
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maxProduct(vector<string>& words) {
    int n = words.size();
    int mask[n];
    memset(mask, 0, sizeof(mask));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (char& c : words[i]) {
        mask[i] |= 1 << (c - 'a');
      }
      for (int j = 0; j < i; ++j) {
        if ((mask[i] & mask[j]) == 0) {
          ans = max(ans, (int) (words[i].size() * words[j].size()));
        }
      }
    }
    return ans;
  }
};

func maxProduct(words []string) (ans int) {
  n := len(words)
  mask := make([]int, n)
  for i, s := range words {
    for _, c := range s {
      mask[i] |= 1 << (c - 'a')
    }
    for j, t := range words[:i] {
      if mask[i]&mask[j] == 0 {
        ans = max(ans, len(s)*len(t))
      }
    }
  }
  return
}

function maxProduct(words: string[]): number {
  const n = words.length;
  const mask: number[] = Array(n).fill(0);
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    for (const c of words[i]) {
      mask[i] |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
    }
    for (let j = 0; j < i; ++j) {
      if ((mask[i] & mask[j]) === 0) {
        ans = Math.max(ans, words[i].length * words[j].length);
      }
    }
  }
  return ans;
}

方法二

class Solution:
  def maxProduct(self, words: List[str]) -> int:
    mask = defaultdict(int)
    ans = 0
    for s in words:
      a = len(s)
      x = 0
      for c in s:
        x |= 1 << (ord(c) - ord("a"))
      for y, b in mask.items():
        if (x & y) == 0:
          ans = max(ans, a * b)
      mask[x] = max(mask[x], a)
    return ans

class Solution {
  public int maxProduct(String[] words) {
    Map<Integer, Integer> mask = new HashMap<>();
    int ans = 0;
    for (var s : words) {
      int a = s.length();
      int x = 0;
      for (char c : s.toCharArray()) {
        x |= 1 << (c - 'a');
      }
      for (var e : mask.entrySet()) {
        int y = e.getKey(), b = e.getValue();
        if ((x & y) == 0) {
          ans = Math.max(ans, a * b);
        }
      }
      mask.merge(x, a, Math::max);
    }
    return ans;
  }
}

class Solution {
public:
  int maxProduct(vector<string>& words) {
    unordered_map<int, int> mask;
    int ans = 0;
    for (auto& s : words) {
      int a = s.size();
      int x = 0;
      for (char& c : s) {
        x |= 1 << (c - 'a');
      }
      for (auto& [y, b] : mask) {
        if ((x & y) == 0) {
          ans = max(ans, a * b);
        }
      }
      mask[x] = max(mask[x], a);
    }
    return ans;
  }
};

func maxProduct(words []string) (ans int) {
  mask := map[int]int{}
  for _, s := range words {
    a := len(s)
    x := 0
    for _, c := range s {
      x |= 1 << (c - 'a')
    }
    for y, b := range mask {
      if x&y == 0 {
        ans = max(ans, a*b)
      }
    }
    mask[x] = max(mask[x], a)
  }
  return
}

function maxProduct(words: string[]): number {
  const mask: Map<number, number> = new Map();
  let ans = 0;
  for (const s of words) {
    const a = s.length;
    let x = 0;
    for (const c of s) {
      x |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
    }
    for (const [y, b] of mask.entries()) {
      if ((x & y) === 0) {
        ans = Math.max(ans, a * b);
      }
    }
    mask.set(x, Math.max(mask.get(x) || 0, a));
  }
  return ans;
}