2306.Naming a Company

tags: Hard,Array,String,Hash Table,Bit Manipulation

2306. Naming a Company

題目描述

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.

Example 2:

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

Constraints:

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

解答

C++

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string> groups[26];
        for (const auto& idea : ideas) {
            groups[idea[0] - 'a'].insert(idea.substr(1));
        }
        long long ans = 0;
        for (int i = 0; i < 25; i++) {
            for (int j = i + 1; j < 26; j++) {
                long long overlap = 0;
                for (const auto& word: groups[i]) {
                    overlap += groups[j].count(word);
                }
                ans += 2 * (groups[i].size() - overlap) * (groups[j].size() - overlap);
            }
        }
        return ans;
    }
};

Yen-Chi ChenThu, Feb 9, 2023

思路:

1. 選兩個idea, 交換第一個char, 若交換後的單字沒出現在原本的輸入即為合法名字, 找出所有合法名字的數量
2. 交換後若有跟輸入重複者, 代表兩個idea第二個字元後開始後綴一樣
3. 可以第一個字元做分組, 每兩組比較個數, 扣除一樣的後綴數量相乘即此兩組可形成的合法數量

Time:

$O(n\ast m)$ m為平均idea長度, 共有26*25/2=325個pair group比較, 每個pair group比較花

$O(n\ast m)$
Extra Space:

$O(n\ast m)$

XD Feb 9, 2023

Python

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        groups = [set() for _ in range(26)]
        for idea in ideas:
            groups[ord(idea[0]) - ord('a')].add(idea[1:])
        ans = 0
        for i in range(25):
            for j in range(i + 1, 26):
                overlap = len(groups[i] & groups[j])
                ans += 2 * (len(groups[i]) - overlap) * (len(groups[j]) - overlap)
        return ans

Yen-Chi ChenThu, Feb 9, 2023

Reference

回到題目列表