台州建站程序百度经验app下载

刷题前唠嗑

LeetCode? 启动！！！

题目：最大单词长度乘积

题目链接：318. 最大单词长度乘积

题目描述

代码与解题思路

不含公共字母的两个字符串的最大乘积，这要是一个个遍历求解，那得有多暴力啊，我选择直接开摆。。。偷看一眼题解看看有什么好方法

偷看大佬题解

。。。

怎么全是位运算啊。。。这个月到处都是位运算要把我弄疯啦

func maxProduct(words []string) (ans int) {marks := [1000]int{}for i, v := range words {t := 0for j := 0; j < len(v); j++ { // 用 int 的低 26 位来代指字母 a-z 是否出现u := v[j]-'a't |= 1<<u}marks[i] = t}for i := 0; i < len(words); i++ {for j := 0; j < i; j++ {if (marks[i]&marks[j]) == 0 { // 每个字符串对应的两个 int 执行 & 操作ans = max(ans, len(words[i])*len(words[j]))}}}return ans
}func max(a, b int) int {if a > b {return a}return b
}

这道题使用位运算的关键其实就是两句话：

1. 我们使用一个 int 的低 26 位来代指字母 a-z 是否出现
2. 每个字符串对应的两个 int 执行 & 操作，如果两字符无重复字符，则结果为 0

就是从 int 的二进制中拿 26 个位置来表示这个字符串的 26 个字母有没有出现，通过 | 操作标记，再通过 & 操作判断是否存在重复字符。

这里我开局开了一个 1000 的数组，主要是题目样例说有 1000 个字符串，所以我就直接开 1000 了，算是之前打算法竞赛的小习惯吧

至于哈希优化，饶了我吧。。。摆了

结语

没啥可说的，总之能过就行~