Imgcity

Appearance

Imgcity✍️ Online Judge 題解LeetCode2306 - Naming a Company

2306 - Naming a Company ​

題目 ​

LeetCode Problem

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:

  1. Choose 2 distinct names from ideas, call them ideaA and ideaB.
  2. Swap the first letters of ideaA and ideaB with each other.
  3. 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.
  4. Otherwise, it is not a valid name.

Return the number of distinct valid names for the company.

說明 ​

我自己先想了一個解法：

先把資料處理成 map: idea[0] -> set of idea[1:]， 然後就可以發現任兩個【第一個字元】所做出的 valid company name 會是|(set1−set2)(set2−set1)|，這樣時間複雜度會是 O(262Nlg⁡N)，空間複雜度是 O(Nlg⁡N)。

Tips:

  • 要對 idea[1:] 做離散化，減少 set<idea[1:]> 的操作常數。
  • 計算 set1 - set2 時，可以只迭代較小的 set。

不過後來我看題解是有用另外的解法。我把問題切成 (i, j) 互換，題解再切了一半：只考慮 i → j 的情況，也就是去數多少個 i 可以換到 j 。最後只要把 (|i→j||j→i|) 加起來就好。

Tips:

  • 可以用 std::string_view

Code: 我的作法 ​

cpp
class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        // 離散化
        map<string, int> strIdx;
        for (const auto& s: ideas) {
            auto suffix = s.substr(1);
            if (strIdx.count(suffix)) {
                continue;
            }

            strIdx[suffix] = strIdx.size();
        }
        
        vector<set<int>> headTail(26);
        for (const auto& s: ideas) {
            headTail[s[0] - 'a'].insert(strIdx[s.substr(1)]);
        }
        
        int64_t ans = 0;
        for (int lx = 0; lx < 26; ++lx) {
            for (int ly = lx+1; ly < 26; ++ly) {
                ans += count(headTail[lx], headTail[ly])*2;
            }
        }
        
        return ans;
    }
    
private:
    int64_t count(const set<int>& a, const set<int>& b) {
        int64_t sz1 = a.size();
        int64_t sz2 = b.size();
        if (sz1 > sz2) {
            for (const auto& s: b) {
                if (a.find(s) != a.end()) {
                    --sz1;
                    --sz2;
                }
            }    
        } else {
            for (const auto& s: a) {
                if (b.find(s) != b.end()) {
                    --sz1;
                    --sz2;
                }
            }
        }
        
        return sz1*sz2;
    }
};

Code: 題解 ​

cpp
class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string_view> ideasSet(ideas.begin(), ideas.end());
        vector<vector<int>> tab(26, vector<int>(26, 0));
        for (const auto& idea: ideas) {
            int i = idea[0] - 'a';
            string tmp = idea;
            for (int j = 0; j < 26; ++j) {
                tmp[0] = 'a' + j;
                if (ideasSet.find(tmp) == ideasSet.end()) {
                    ++tab[i][j];
                }
            }
        }
        
        int64_t ans = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                ans += int64_t(tab[i][j])*tab[j][i];
            }
        }
        
        return ans;
    }
};

Changelog

Just observe 👀