【动态规划】2306. 公司命名

本文涉及知识点

动态规划汇总

LeetCode 2306. 公司命名

给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
从 ideas 中选择 2 个不同名字，称为 ideaA 和 ideaB 。
交换 ideaA 和 ideaB 的首字母。
如果得到的两个新名字都不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
否则，不是一个有效的名字。
返回不同且有效的公司名字的数目。
示例 1：
输入：ideas = [“coffee”,“donuts”,“time”,“toffee”]
输出：6
解释：下面列出一些有效的选择方案：

(“coffee”, “donuts”)：对应的公司名字是 “doffee conuts” 。
(“donuts”, “coffee”)：对应的公司名字是 “conuts doffee” 。
(“donuts”, “time”)：对应的公司名字是 “tonuts dime” 。
(“donuts”, “toffee”)：对应的公司名字是 “tonuts doffee” 。
(“time”, “donuts”)：对应的公司名字是 “dime tonuts” 。
(“toffee”, “donuts”)：对应的公司名字是 “doffee tonuts” 。
因此，总共有 6 个不同的公司名字。

下面列出一些无效的选择方案：

(“coffee”, “time”)：在原数组中存在交换后形成的名字 “toffee” 。
(“time”, “toffee”)：在原数组中存在交换后形成的两个名字。
(“coffee”, “toffee”)：在原数组中存在交换后形成的两个名字。
示例 2：

输入：ideas = [“lack”,“back”]
输出：0
解释：不存在有效的选择方案。因此，返回 0 。

提示：
2 <= ideas.length <= 5 * 10⁴
1 <= ideas[i].length <= 10
ideas[i] 由小写英文字母组成
ideas 中的所有字符串互不相同

动态规划的状态表示

n = ideas.length
m = ideas[i].length
dp[j][k] 表示处理完ideas[0…i-1]，符合以下条件的ideas数量：
首字母可以换成‘a’+j，首字符为’a’+k。
空间复杂度：O( $\sum\sum$ ) $\sum$ 是字符集的大小，此处为26。

动态规划的转移方程

tmp = ideas[i];
for( j = 0 ; j < 26;j++)
{
tmp[0] = ‘a’+j;
如果tmp不存在 dp[j][ideas[i][0]-‘a’]++;
}
单个状态的转移方程时间复杂度：O(m+ $\sum$ )
总时间复杂度：O(n $\times (m+\sum)$ )

动态规划的初值

全为0。

动态规划的填表顺序

i从0到大

动态规划的返回值

tmp = ideas[i];
for( j = 0 ; j < 26;j++)
{
tmp[0] = ‘a’+j;
如果tmp不存在 ret += dp[ideas[i][0]-‘a’][j]
}
最终返回值：ret*2 ，只枚举了下标小的在前面，其实下标小的可以在后面。
** 注意** ：返回值的循环和转移方程的循环不能合并，且先处理返回值。

代码

核心代码

class Solution{
public:
	long long distinctNames(vector<string>&ideas) {
		int dp[26][26] = { 0 };
		unordered_set<string> sHas(ideas.begin(), ideas.end());
		long long ret = 0;
		for (const auto& s : ideas) {
			const int inx = s[0] - 'a';
			auto tmp = s;
			for (int j = 0; j < 26; j++) {
				tmp[0] = 'a' + j;
				if (!sHas.count(tmp)) {
					ret += dp[inx][j];
				}
			}
			for (int j = 0; j < 26; j++) {
				tmp[0] = 'a' + j;
				if (!sHas.count(tmp)) {
					dp[j][inx]++;
				}
			}
		}
		return ret*2;
	}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}



namespace UnitTest
{	
	vector<string> ideas;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod00)
		{
			ideas = { "coffee", "donuts", "time", "toffee" };
			auto res = Solution().distinctNames(ideas);
			AssertEx(6LL, res);
		}
		TEST_METHOD(TestMethod01)
		{
			ideas = { "lack","back" };
			auto res = Solution().distinctNames(ideas);
			AssertEx(0LL, res);
		}
	};
}

返回值优化

累加：dp[i][j]和dp[j][i]相乘

class Solution{
public:
	long long distinctNames(vector<string>&ideas) {
		int dp[26][26] = { 0 };
		unordered_set<string> sHas(ideas.begin(), ideas.end());		
		for (const auto& s : ideas) {
			const int inx = s[0] - 'a';
			auto tmp = s;
			for (int j = 0; j < 26; j++) {
				tmp[0] = 'a' + j;
				if (!sHas.count(tmp)) {
					dp[j][inx]++;
				}
			}
		}
		long long ret = 0;
		for (int i = 0; i < 26; i++) {
			for (int j = 0; j < 26; j++) {
				ret += (long long)dp[i][j] * dp[j][i];
			}
		}
		return ret;
	}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛