2306. Naming a Company
給你一個有很多單字的 array 叫做 ideas，要你用他組成一個新的公司名字，流程是:
1.挑兩個單字 例如:"coffee", "donuts"
2.交換他們第一個字母 -> "doffee", "conuts"
3.檢查交換後的兩個字有沒有在原本的 ideas 裡
都沒有的話就可以產出公司名字 "doffee conuts" (新名字不用加進 ideas 裡)
問你可以產出多少種名字
Example 1:
Input: ideas = ["coffee","donuts","time","toffee"]
Output: 6
Explanation:
合法的名字有:
- ("coffee", "donuts") -> "doffee conuts".
- ("donuts", "coffee") -> "conuts doffee".
- ("donuts", "time") -> "tonuts dime".
- ("donuts", "toffee") -> "tonuts doffee".
- ("time", "donuts") -> "dime tonuts".
- ("toffee", "donuts") -> "doffee tonuts".
不合法的像是
- ("coffee", "time"): toffee 有在 ideas 裡
- ("time", "toffee"): time 和 toffee 都在 ideas 裡
- ("coffee", "toffee"): toffee 和 coffee 都在 ideas 裡
Example 2:
Input: ideas = ["lack","back"]
Output: 0
Explanation:
沒有合法名字，交換後都在 ideas 裡
思路:
1.如果枚舉任兩個單字然後做檢查，時間複雜度O(n^2)會超時
所以要想個辦法一次算多一點不能一個一個加
觀察發現 axxxxx, byyyy 如果不合法就代表 ayyyy 或是 bxxxxx 在 ideas 裡
也就是 a 開頭的單字中有 yyyy，b 開頭的單字中也有 yyyy
如果我們把單字依開頭字母分類成 26 個 set
就可以一次看 a 開頭的那些單字和 b 開頭的那些單字總共有幾組合法答案
方法就是先剔除掉像是 yyyy 這種同時在兩個 set 裡都有的單字
之後就可以保證說 set[a] 裡的所有單字和 set[b] 裡的所有單字都沒有重複
合法答案總數就是剔除後的 len(set[a])*len(set[b])
這樣就不用枚舉每個單字而是變成枚舉任兩個英文字母之後找出他們重複的元素
時間複雜度變成O(26*26*n)
Python code:
class Solution:
def distinctNames(self, ideas: List[str]) -> int:
body = defaultdict(set)
for idea in ideas:
body[idea[0]].add(idea[1:])
res = 0
for c1 in body:
for c2 in body:
if c1 == c2:
continue
c = len(body[c1] & body[c2])
res += (len(body[c1]) - c) * (len(body[c2]) - c)
return res