3 min read leetcode

2306. Naming a Company

2306. Naming a Company
Photo by Markus Spiske / Unsplash

題目連結: 2306. Naming a Company

題意

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

  1. 選兩個不同的字
  2. 將兩個字的首字母交換
  3. 交換首字母後的新字不能出現在原有的 ideas 中
  4. 兩個單字順序對調後也算一個獨立的答案

限制

  • 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.

Cases

  1. [toffee, time] ⇒ 交換後不變
  2. [coffee, toffee] ⇒ 交換後存在與原本相同的字
  3. [coffee, toffee, time] ⇒ [coffee, time] 互換後會有 toffee 導致重複

思考

  • 由 case 1 思考 ⇒ 當首字母相同時必定不會是答案 ⇒ 將相同首字母的單字群組
  • 由 case 2、3 ⇒ 去除首字母的後綴 (suffix) 也不會是答案 ⇒ 計算兩個群組間可能的答案時，要去掉相同 suffix 的
  • 計算總數
    • 定義
      • 令 S 為所有單字的集合
      • 對於任意單字 w，定義其首字母為 prefix(w)，其餘部分為 suffix(w)
    • 分組
      • 根據首字母分組，對於首字母 p，定義 $$G_p = \{ w \in S \mid \text{prefix}(w) = p \}$$
      • 為每個 G_p​ 提取後綴 $$S_p = \{\text{suffix}(w)\,\mid\, w \in G_p\}$$
    • 計算兩個 group 之間的有效命名數
      • 考慮兩個不同首字母 p 和 q，對應的 G_p​ 與 G_q​： $${overlaps}_{p,q} = |S_p \cap S_q|$$

$${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≠qp \neq qp=q$$，求和 $${total} = \sum_{(p,q)\,\text{distinct}} \text{valid\_names}_{p,q}$$

Coding流程

  • 建立 26 個 set 代表每個首字母
    • 根據 ch - 'a' 分組，並將 suffix 放入 set 中去除重複
  • 透過雙層迴圈，跑過所有的 $${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;
    }
};

時間與空間複雜度

  • 時間複雜度
    • 我們先遍歷整個 ideas 陣列，將每個字串的首字母對應到 suffix 陣列中的一個 unordered_set，此步驟約為 O(N)。
    • 接著，對所有可能的首字母組合（最多 26×26≈676組）進行重疊後綴的檢查。countOverlapped 會遍歷 suffix[p]，對每個後綴以平均 O(1) 時間檢查 suffix[q] 中是否存在相同後綴，所以對每組首字母的檢查約為 O(|G_p|)；由於所有字串總和為 N，整體仍可視為 O(N) 等級。
    • 因此，總時間複雜度大致為 O(N)。
  • 空間複雜度
    • 需要額外儲存所有字串的後綴於 26 個 unordered_set 中，總字串數量不超過 N，因此空間複雜度為 O(N)。

Justin