1 題目

題目來源于力扣第 297 場周賽的困難題，2306. 公司命名：

給你一個字符串?dāng)?shù)組 ideas 表示在公司命名過程中使用的名字列表。公司命名流程如下：

1. 從 ideas 中選擇 2 個 不同 名字，稱為 ideaA 和 ideaB 。

2. 交換 ideaA 和 ideaB 的首字母。

3. 如果得到的兩個新名字 都 不在 ideas 中，那么 ideaA ideaB（串聯(lián) ideaA 和 ideaB ，中間用一個空格分隔）是一個有效的公司名字。

4. 否則，不是一個有效的名字。

返回 不同 且有效的公司名字的數(shù)目。

示例 1：

輸入：ideas?=?["coffee","donuts","time","toffee"]
輸出：6
解釋：下面列出一些有效的選擇方案：
-?("coffee",?"donuts")：對應(yīng)的公司名字是?"doffee?conuts"?。
-?("donuts",?"coffee")：對應(yīng)的公司名字是?"conuts?doffee"?。
-?("donuts",?"time")：對應(yīng)的公司名字是?"tonuts?dime"?。
-?("donuts",?"toffee")：對應(yīng)的公司名字是?"tonuts?doffee"?。
-?("time",?"donuts")：對應(yīng)的公司名字是?"dime?tonuts"?。
-?("toffee",?"donuts")：對應(yīng)的公司名字是?"doffee?tonuts"?。
??因此，總共有?6?個不同的公司名字。

下面列出一些無效的選擇方案：
-?("coffee",?"time")：在原數(shù)組中存在交換后形成的名字?"toffee"?。
-?("time",?"toffee")：在原數(shù)組中存在交換后形成的兩個名字。
-?("coffee",?"toffee")：在原數(shù)組中存在交換后形成的兩個名字。


示例 2：

輸入：ideas?=?["lack","back"]
輸出：0
解釋：不存在有效的選擇方案。因此，返回?0?。


提示：

• 2 <= ideas.length <= 5 * 104

• 1 <= ideas[i].length <= 10

• ideas[i] 由小寫英文字母組成

• ideas 中的所有字符串 互不相同

來源：力扣（LeetCode）

鏈接：https://leetcode.cn/problems/naming-a-company

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2 思路

按照我做題的思路講解一下整個過程吧，前面的幾次代碼無法通過，會超時，但是因?yàn)槠浜啙嵭钥梢苑奖愦蠹依斫馑悸?。前面思路講解部分代碼示例使用的是 Scala。只會 Java 看不懂 Scala 的朋友或者想看最終代碼的朋友，可以只看思路介紹或者跳到最后就好。

最終的代碼分別基于 Java 和 Scala 兩種語言的 BitSet 類庫實(shí)現(xiàn)，沒有使用力扣題解當(dāng)中普遍使用的二維數(shù)組。個人感覺理解起來還是比較方便的，Java 代碼耗時也擊敗了 96.40% （Scala 提交人數(shù)較少，耗時擊敗占比參考價值較低），說明性能也是相當(dāng)不錯的。

會 Java 的話，其實(shí)下面的 Scala 代碼也不難理解（畢竟也不長），大概就是：

1. 鏈?zhǔn)秸{(diào)用中，.groupBy(...) 對應(yīng)成 Java 的 .collect(Collectors.groupingBy(...))，其他按字面意思對應(yīng) Java 8 引入的 Streams API 即可。

2. for 循環(huán)中 .indices 對應(yīng)全部遍歷， 0 until i 對應(yīng)從 0 到 i（不包括 i）。yield 相當(dāng)于是把 for 循環(huán)里面每一步的結(jié)果放到一個序列里面

3. Set 的 diff 方法就是求前面的 Set 去掉后面 Set 元素的差集

根據(jù)題意，我們可以發(fā)現(xiàn)首字母和首字母以外的字符串是本題中的關(guān)鍵。在本篇題解當(dāng)中，我們將首字母以外的字符串簡稱為后綴。

我們可以分析兩個單詞（單詞 a 和單詞 b）不可以組成公司名稱的情況有如下幾個：

1. a 和 b 后綴一致

2. a 的首字母可以和 b 的后綴組成另一個 ideas 中的單詞

3. b 的首字母可以和 a 的后綴組成另一個 ideas 中的單詞

那么我們就可以考慮：將后綴相同的單詞分別按照后綴聚合起來，處理成其首字母的集合，方便我們后續(xù)的計算。例如 ideas = ["coffee", "donuts", "time", "toffee", "koffee", "dime", "conuts"], 將被處理成:

• "offee": ['c','k','t']

• "onuts": ['c','d']

• "ime": ['d','t']

觀察兩個集合之間能夠組成公司的名稱的選擇，比如 "offee" 和 "onuts" 后綴。我們最終選出來的是 "offee" 中的 'k','t' 和 "onuts" 的 'd'，他們可以搭配成 ["koffee","donuts"] 組合與 ["toffee","donuts"] 組合（當(dāng)然，還有它們的反序組合，一共四個）。其特點(diǎn)就是在后綴 "offee" 的首字符集合和后綴 "onuts" 首字符集合中把都出現(xiàn)過的 'c' 去掉，然后兩個集合就可以兩兩組合成公司名稱了。那么個數(shù)就是兩個集合的個數(shù)分別減去交集個數(shù)，然后乘起來，也就是 (3 - 1) * (2 - 1) = 2（因?yàn)榉葱蛞部梢?，再乘?2，得到 4 個）。

按照同樣的邏輯兩兩計算，最后我們得到 4 ("offee" 和 "onuts") + 2 ("onuts" 和 "ime") + 4 ("offee" 和 "ime") = 10。符合我們示例的對應(yīng)結(jié)果（不信的話，你可以直接在力扣測試?yán)锩嬖?，啊哈哈）?/p>

那么問題就轉(zhuǎn)化為如下思路：將單詞處理成首字母和后綴；然后以其中之一為聚合項（這里我們選擇的是后綴），把另一項聚合在集合里；再把集合相互之間求差，然后相乘。把結(jié)果加起來就是要求的個數(shù)。

需要注意的是，選擇首字母作為聚合項也是可以的。后面優(yōu)化會用到這一點(diǎn)。

那么最簡單的實(shí)現(xiàn)如下：

這里因?yàn)?i 和 j 的差集相乘計算會等同于 j 和 i 的差集相乘計算，所以我們用限制 j < i 和最后對結(jié)果 * 2 略微優(yōu)化了一下。

可惜上述代碼將在最后幾個數(shù)據(jù)量較大的測試用例超時。

那么我們有什么辦法來優(yōu)化耗時呢？很顯然上述操作當(dāng)中，val sets 的計算過程時間復(fù)雜度就是 O(n * m), n 是不同首字母以外字符串的個數(shù)，m 是首字母位集的大小。這里也沒有太多的優(yōu)化空間。

但是后面的 for 循環(huán)時間復(fù)雜度是 O(n^2?* m)，其中 O(n^2)?的時間復(fù)雜度是 for 循環(huán)本身引入的，O(m) 是由 Set diff 操作引入的。這個時間復(fù)雜度更高，我們需要重點(diǎn)關(guān)注這里能如何優(yōu)化。

Set 的 diff 操作會比較耗時，因?yàn)檫@里面會涉及到 Set 的遍歷和重建。那么我們就可以考慮使用位集的思想來優(yōu)化。這里因?yàn)榍懊嫖覀兘⒌募鲜?strong>首字符的集合，位集的位數(shù)不會超過 26（小寫英文字母的個數(shù)），所以位集的實(shí)現(xiàn)就更加簡單了，我們暫時可以使用自行實(shí)現(xiàn)的位集邏輯而無須使用類庫中的 BitSet。

使用位運(yùn)算優(yōu)化集合求差的操作的實(shí)現(xiàn)代碼如下：

很遺憾，這個代碼還是超時了，那么說明 set 的 diff 還不是最耗時的瓶頸，畢竟時間復(fù)雜度本身的量級并沒有改變。

繼續(xù)觀察，可以發(fā)現(xiàn)選擇后綴來作為聚合項可能并不是一個好的選擇，這樣導(dǎo)致后續(xù)兩兩對首字母位集做處理的時間復(fù)雜度是 O(n^2 * m)，n 是不同首字母以外字符串的個數(shù)，m 是首字母位集的大小。這里 m 小于 26，但是 n 在單詞特別多時，卻可以沒有上限地上漲。那么我們可以把 m 理解為常數(shù)項，時間復(fù)雜度為 O(n^2)。 那么我們就可以想到：應(yīng)該選擇首字母作為聚合項，而將聚合的后綴的集合處理成位集。這樣處理的話，時間復(fù)雜度可以下降為 O(n)（這里還是把 m 視為常數(shù)了，如果要視為變量的話，就乘個 m 平方）

因?yàn)楹缶Y個數(shù)是沒有上限的，所以我們不能繼續(xù)使用我們自定義的位集了，這里我們應(yīng)該使用類庫提供的 BitSet。而為了將字符串轉(zhuǎn)換為位數(shù)，我們需要存儲一個映射保留這個信息。

最終的思路就是：

1. 把相同首字母的單詞收集到 Map 里，key 是首字母，value 是這些單詞去掉首字母后的字符串組成的 List。

2. 將 value List 處理成對應(yīng)的位集（BitSet）List。為了達(dá)到這個目的，我們需要維護(hù)一個 hash 映射表，里面存儲的是字符串和它對應(yīng)的bitSet 索引（即第幾位用來表示該字符串是否存在）

3. 經(jīng)過上面的處理的 BitSet List，我們兩兩計算其 bitset(i) 去除 bitset(j) 中元素后的元素數(shù)量(即 Scala 的 &~（Java 的 andNot）操作求差集)乘以 bitset(j) 去除 bitset(i) 中元素后的元素數(shù)量的積。這里是對應(yīng)首字母不同的情況處理出來的 BitSet 兩兩之間。

3 通過代碼

最后通過的代碼：

Java

Scala

4 題外話

吐槽一下： 一開始自己按C(2,n)的組合數(shù)減掉不可以組合的思路整了半天整不出來，想看題解了解一下別人的思路，可能是各種沒注釋的縮寫變量名看得我腦殼疼，也可能是我太蠢了或者沒耐心，所有的那種建個二維數(shù)組的方法我看了大半個小時也沒看懂…… 那就只能自己整了，好歹最后還是做出來了，方法和一般的題解不太一樣，直接用到了 BitSet 優(yōu)化集合求差的耗時。 我看好像 Java 那么多提交里面也沒怎么看到類似的實(shí)現(xiàn)，分享一下供大家參考，耗時排名其實(shí)也挺能打的，Java 擊敗 96.40%。

后來回過頭還是模模糊糊看懂了二維數(shù)組的方法：

1. 其中也會維護(hù)一個 ideas 按后綴聚合的存儲首字母集合的 Map——也有的題解中用位集思想優(yōu)化了。

2. 只是在這里還引入了一個二維數(shù)組存儲整個 ideas 當(dāng)中首字母有 i 無 j 的個數(shù)，然后就可以在遍歷 ideas 的過程中對所有的 26 個字母查 Map 確認(rèn)當(dāng)前后綴是否已經(jīng)有過同后綴的其他首字母，然后維護(hù)這個二維數(shù)組（i 無法與多少個 j 開頭的字符串交換，以及反之）。

雖然看懂了，但是感覺這個思維模式還是和我自己沖突，有點(diǎn)打腦袋…… 要是你也有類似感覺的話，希望我這個思路可以幫到你，我自己感覺我的思路還是理解起來更直觀一點(diǎn)的。