【LeetCode】每日一题 2023_11_6 最大单词长度乘积

文章目录

• 刷题前唠嗑
• 题目：最大单词长度乘积
• 结语

刷题前唠嗑

LeetCode? 启动！！！

题目：最大单词长度乘积

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

题目描述

代码与解题思路

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

偷看大佬题解

。。。

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

func maxProduct(words []string) (ans int) {
    marks := [1000]int{}
    for i, v := range words {
        t := 0
        for 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 了，算是之前打算法竞赛的小习惯吧

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

结语

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