leetcode周赛297记录

nth2000

于 2022-06-12 19:14:06 发布

阅读量183

点赞数

文章标签： leetcode 算法

本文链接：https://blog.csdn.net/nth2000/article/details/125248690

版权

在这里插入图片描述

思路

注意小写英文字母，枚举即可
令 $c n t [i] [j]$ -将字母i变为字母j后不在原始字符串中的字符串数目
每个字符串上，枚举变化后的首字母

class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        long long cnt[26][26];
		for(int i = 0;i<26;i++) memset(cnt[i],0,26*sizeof(long long));
		unordered_set<string> c;
		for(string& s:ideas) c.insert(s);
		for(string&s:ideas)
		{
			char f = s[0];
			for(char d = 'a';d<='z';d++)
			{
				if(d!=f && c.find(d+s.substr(1)) == c.end()) cnt[f - 'a'][d - 'a']++;
			}
		}
		long long ans = 0;
		for(string& p : ideas)
		{
			char f = p[0];
			for(char d = 'a';d<='z';d++)
			{
				if(c.find(d+p.substr(1)) == c.end())  //可以替换
				ans+= cnt[d - 'a'][f - 'a'];
			}
		}
		return ans;
    }
};