LeetCode6094 公司命名

发表于 | 分类于 |
字数统计: 323 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/naming-a-company/

题意

周赛第四题
给定一个字符串数组
要求将其中任意两个字符串交换首字母 且交换后的字符串在原数组中没有出现过
求组合的个数

解法

通过set记录原有字符串。对每一个字符串改变第一位判断是否可以进行变换，并记录在alpha[a][b]中
表示以a为首的字符串 首字母换成b后不重复的字符串个数
最后在alpha中寻找两两对应关系即可找出可交换组数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        vector<vector<int>> alpha(30, vector<int>(30));
        // alpha[a][b]表示以a为首的字符串 首字母换成b后不重复的字符串个数
        unordered_set<string> st(ideas.begin(), ideas.end());
        int n = ideas.size();
        for (auto s: ideas) {
            int origin = s[0] - 'a';
            for (int i = 0; i < 26; i++) {
                s[0] = 'a' + i;
                // 将以当前字符串开头换成26种字母后，对应每种首字母 不重复的个数
                if (!st.count(s)) alpha[origin][i]++;
            }
        }
        long long ans = 0;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                ans += alpha[i][j] * alpha[j][i];
            }
        }
        return ans;
    }
};