最大单词长度乘积

两两配对本身省不掉(这是 O(n²) 对),真正慢的是每对都要逐字母比「有没有公共字母」。能不能把这步变成一眨眼?

把每个词压成一个整数:第 0 位代表 a、第 1 位代表 b……第 25 位代表 z。词里出现某字母,对应位就置 1。两个词按位与 = 0 就说明没有公共字母——一次运算搞定!

第一步 · 把每个词压成掩码：把单词的字母摊开成一排。先处理 abcw:掩码从 0 开始,扫到一个字母就把它对应的位置 1。

abcw · 读到 'a'：指针落在 a。a 排第 0,就把掩码第 0 位置 1,这格点亮。掩码现在记着 {a}。

abcw · 读到 'b'：指针挪到 b(第 1 个),点亮第 1 位。已点亮的格子累积成 {a, b}。

abcw · 读到 'c'：指针到 c(第 2 个),点亮第 2 位。掩码 {a, b, c}。

abcw · 读到 'w'：最后到 w(第 22 个字母),点亮第 22 位。abcw 扫完,掩码 = {a, b, c, w},四个开关亮着。这个整数就代表了 abcw 用过的所有字母。

六个词全压成掩码：同样手法把六个词都压成掩码(foo 有两个 o,但位掩码只管有没有、不管几个,所以是 {f,o})。现在每个词就是一个整数。下面让 abcw 当主角,和后面每个词两两按位与。

配对 · abcw × baz：固定 abcw(绿),和 baz 按位与,结果留下 {a,b}——不为 0,两词共用了 a、b,不能配。

配对 · abcw × foo：abcw 和 foo 按位与 = 0,没有公共字母,可以配!长度 4 × 3 = 12。best 更新成 12(baz 已比过变灰)。

配对 · abcw × bar：abcw 和 bar 共用 a、b,按位与不为 0,跳过。best 还是 12。

配对 · abcw × xtfn · 关键一对!：重头戏:abcw 和 xtfn 按位与 = 0!字母完全不沾边,4 × 4 = 16。best 刷新成 16——这就是最终答案。

配对 · abcw × abcdef：abcw 配 abcdef 共用 a、b、c,跳过。abcw 这一轮配对结束,best = 16。

换主角 · baz × foo：abcw 封存变灰,换 baz 当主角。baz 和 foo 能配,但 3×3=9 追不上 16。

baz × bar：baz 和 bar 共用 a、b,跳过。

baz × xtfn：baz 和 xtfn 能配,但 3×4=12 还是追不过 16。

换主角 · foo × bar：再换 foo 当主角,foo 和 bar 能配,9 < 16。

foo × xtfn：foo 和 xtfn 都含 f,按位与留下 {f},跳过。

bar × xtfn：bar × xtfn 能配,12 仍追不过 16。

最后 · xtfn × abcdef：最后一对 xtfn × abcdef 都含 f,按位与留下 {f},跳过。所有 15 对都比完了。

全部配对完成 · 答案 = 16：所有 15 对都比过一遍,最大乘积来自绿色的 abcw × xtfn,答案 16。位掩码把每对的「逐字母比对」压成了一次按位与。

雷区实演 · 把 == 0 写成 != 0：假如把条件写反成 != 0 才更新,真正合法的 abcw×xtfn(按位与=0)反而被跳过,答案就错了。按位与为 0 才是「无公共字母 = 可配」。

边界三连：先想清「全冲突返回 0」「只有一对」「不足两个词」三种边界,代码就稳了。

面试追问：把「为何用位掩码」「& 判重叠为何 O(1)」讲清楚,是这题面试的得分点。