您现在的位置：程式師世界 >> 編程語言 > >> 更多編程語言 >> Python

leetcode 2306. Naming a Company （python）

編輯：Python

Keep creating , Accelerate growth ！ This is my participation 「 Nuggets day new plan · 6 Yuegengwen challenge 」 Of the 28 God , Click to see the event details

describe

You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:

Choose 2 distinct names from ideas, call them ideaA and ideaB.
Swap the first letters of ideaA and ideaB with each other.
If both of the new names are not found in the original ideas, then the name ideaA ideaB (the concatenation of ideaA and ideaB, separated by a space) is a valid company name.
Otherwise, it is not a valid name.

Return the number of distinct valid names for the company.

Example 1:

Input: ideas = ["coffee","donuts","time","toffee"]
Output: 6
Explanation: The following selections are valid:
- ("coffee", "donuts"): The company name created is "doffee conuts".
- ("donuts", "coffee"): The company name created is "conuts doffee".
- ("donuts", "time"): The company name created is "tonuts dime".
- ("donuts", "toffee"): The company name created is "tonuts doffee".
- ("time", "donuts"): The company name created is "dime tonuts".
- ("toffee", "donuts"): The company name created is "doffee tonuts".
Therefore, there are a total of 6 distinct company names.
The following are some examples of invalid selections:
- ("coffee", "time"): The name "toffee" formed after swapping already exists in the original array.
- ("time", "toffee"): Both names are still the same after swapping and exist in the original array.
- ("coffee", "toffee"): Both names formed after swapping already exist in the original array.
 Copy code

Example 2:

Input: ideas = ["lack","back"]
Output: 0
Explanation: There are no valid selections. Therefore, 0 is returned.
 Copy code

Note:

2 <= ideas.length <= 5 * 10^4
1 <= ideas[i].length <= 10
ideas[i] consists of lowercase English letters.
All the strings in ideas are unique.
 Copy code

analysis

According to the meaning , Given an array of strings ideas , Represents a list of words used to name a company . The company naming process is as follows ：

Choose from ideas 2 Different names , Known as ideaA and ideaB.
In exchange for ideaA and ideaB The first letter of .
If these two new names are not found in the original idea , Then name ideaA ideaB Is a valid company name . otherwise , It is not a valid name .

Returns the number of different valid names for the company .

This question examines the use of a set , We want to know ideas The number of legal company names , Just focus on the first two letters and the parts after them , Define a dictionary d in , The objects stored inside are collections . Let's first traverse ideas , Put the substrings of the same initial starting from the first character into a set , Then we compare the set corresponding to the current key in the dictionary v1 Set corresponding to other keys v2 The intersection that can be formed s , Then the effective company name formed by these two keys is (len(v1)-len(s)) * (len(v2)-len(s)) * 2 , Add it to result , Let's compare the other two different keys , Finally back to result Is the answer .

The time complexity is O(N) , The space complexity is O(N) .

answer

class Solution(object):
def distinctNames(self, ideas):
"""
:type ideas: List[str]
:rtype: int
"""
d = collections.defaultdict(set)
for idea in ideas:
d[idea[0]].add(idea[1:])
result = 0
keys = list(d.keys())
N = len(keys)
for i in range(N):
for j in range(i+1, N):
k1,k2 = keys[i],keys[j]
v1,v2 = d[k1],d[k2]
s = v1 & v2
if k1 != k2:
result += (len(v1)-len(s)) * (len(v2)-len(s)) * 2
return result
 Copy code

Running results

Runtime: 544 ms, faster than 91.67% of Python online submissions for Naming a Company.
Memory Usage: 33 MB, less than 47.92% of Python online submissions for Naming a Company.
 Copy code