318.最大单词长度乘积.md

318.最大单词长度乘积

/*
 * @lc app=leetcode.cn id=318 lang=typescript
 *
 * [318] 最大单词长度乘积
 */

// @lc code=start
function maxProduct(words: string[]): number {}
// @lc code=end

解法 1: 朴素解法

function maxProduct(words: string[]): number {
  let max = 0
  for (let i = 0; i < words.length - 1; i++) {
    const set = new Set(words[i])
    nextWord: for (let j = i + 1; j < words.length; j++) {
      for (const char of words[j]) {
        if (set.has(char)) continue nextWord
      }
      max = Math.max(max, words[i].length * words[j].length)
    }
  }
  return max
}

解法 2: 位运算

使用一个数字表示单词所包含的字母,数字二进制的 126 位分别对应 az.先预处理数组,计算每个单词所对应的这样一个数字,然后通过将两个单词对应的数字进行与运算可以在 O(1) 的时间判断两个单词是否有重复的字符.

function maxProduct(words: string[]): number {
  const n = words.length
  let max = 0

  const map: number[] = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    for (const char of words[i]) {
      map[i] = map[i] | (1 << (char.charCodeAt(0) - 'a'.charCodeAt(0)))
    }
  }
  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (map[i]! & map[j]!) continue

      max = Math.max(max, words[i].length * words[j].length)
    }
  }
  return max
}

Case

test.each([
  {
    input: { param: ['abcw', 'baz', 'foo', 'bar', 'xtfn', 'abcdef'] },
    output: 16,
  },
  { input: { param: ['a', 'ab', 'abc', 'd', 'cd', 'bcd', 'abcd'] }, output: 4 },
  { input: { param: ['a', 'aa', 'aaa', 'aaaa'] }, output: 0 },
])('input: param = $input.param', ({ input: { param }, output }) => {
  expect(maxProduct(param)).toEqual(output)
})