2306. Naming a Company

題意

給一個陣列的字串 ideas，計算可以用命名的總和，規則如下

1. 選兩個不同的字

2. 將兩個字的首字母交換

3. 交換首字母後的字不能出現在原有的 ideas中

4. 兩個單字順序對調後也算一個獨立的答案

限制

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

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

• ideas[i] consists of lowercase English letters.

• All the strings in ideas are unique.

Cases

1. [toffee, time] ⇒ 交換後不變

2. [coffee, toffee] ⇒ 交換後存在與原本相同的字

3. [coffee, toffee, time] ⇒ [coffee, time] 互換後會有 toffee導致重複

思考

• 由 case 1 思考 ⇒ 當首字母相同時必定不會是答案 ⇒ 將相同首字母的單字群組

• 由 case 2, 3 ⇒ 去除首字母的後綴(suffix)也不會是答案 ⇒ 計算兩個群組間可能的答案時要去掉相同suffix的

• 計算總數

  • 定義

    • 令 $S$ 為所有單字的的集合

    • 動於任意的單字 $w$，定義其首字母為 $\text{prefix}(w)$，其餘部分為 $\text{suffix}(w)$

  • 分組

    • 根據首字母分組，對於首字母 $p$，定義為 $G_p = \{ w \in S | \text{prefix}(w) = p \}$

    • 為每個 $G_p$ 提取後綴 $S_p = \{ \text{suffix}(w)| w \in G_p \}$

  • 計算兩個group之間的有效命名數

    • 考慮兩個不同首字母 $p$ 和 $q$，$G_p$ 和 $G_q$

      • 重複的suffix: $\text{overlaps}_{p,q} = |S_p \cap S_q|$

      • $\text{valid\_names}_{p,q} = (|G_p| - \text{overlaps}_{p,q})\times (|G_q| - \text{overlaps}_{p,q}) \times 2$

        • 根據規則4，交換也是可以的，因此要乘上2

  • 計算總數

    • 對所有不同的字母 pair $(p,q)$，$p \neq q$，所有的總和

    • $\text{total} = \sum_{(p,q)\text{distinct}} \text{valid\_names}_{p,q}$

Coding流程

• 建立26個set代表每個首字母

  • 根據 ch - ‘a’分組並將suffix放入set去除重複的部分

• 透過雙層迴圈，跑過所有的 $\text{valid\_names}_{p,q}$，並將結果加總

for (i in 0..25)
  for (j in i + 1 .. 26)

Solution

class Solution {
    vector<unordered_set<string>> suffix;

    int countOverlapped(int p, int q) {
        int count = 0;
        for (const string& s : suffix[p]) {
            if (suffix[q].count(s)) {
                count += 1;
            }
        }
        return count;
    }
    
public:
    long long distinctNames(vector<string>& ideas) {
        const int n = ideas.size();
        long long ans = 0;
        suffix.resize(26);

        for (const auto& idea : ideas) {
            suffix[idea[0] - 'a'].insert(idea.substr(1));
        }

        for (int p = 0; p < 25; p += 1) {
            for (int q = p + 1; q < 26; q += 1) {
                int count = countOverlapped(p, q);
                ans += (suffix[p].size() - count) * (suffix[q].size() - count) * 2;
            }
        }
        return ans;
    }
};