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

我很想扁你==

恶心

大师