【动态规划】【记忆化搜索】【回文】1312让字符串成为回文串的最少插入次数

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总
记忆化搜索回文字符串

LeetCode1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的最少操作次数。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = “mbadm”
输出：2
解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3：
输入：s = “leetcode”
输出：5
解释：插入 5 个字符后字符串变为 “leetcodocteel” 。
提示：
1 <= s.length <= 500
s 中所有字符都是小写字母。

动态规划

动态规划的状态表示

dp[left][r] 表示s[left,r]变成回文需要插入的字符数。

动态规划的转移方程

$dp[left][r]=min\begin{cases} dp[left+1][r-1] & s[left]==s[r] \\ dp[left+1][r]+1 & \\ dp[left][r-1]+1 & \\ \end{cases}$
用Cal函数代替dp向量：一，方便记忆。二，方便处理left > r。

动态规划的初始值

全为-1，表示未处理。

动态规划的填表顺序

递归计算dp[0][n-1]

动态规划的返回值

dp[0][n-1]

代码

核心代码

class Solution {
public:
	int minInsertions(string s) {
		const int n = s.length();
		vector<vector<int>> dp(n, vector<int>(n, -1));
		return Cal(dp,s,0, n - 1);
	}
	int Cal (vector<vector<int>>& dp ,const string& s,int left, int r)
	{
		if (left > r)
		{
			return 0;
		}
		if (-1 != dp[left][r])
		{
			return dp[left][r];
		}
		if (s[left] == s[r])
		{
			return dp[left][r] = Cal(dp,s,left + 1, r - 1);
		}
		return dp[left][r] = min(Cal(dp, s, left + 1, r) + 1, Cal(dp, s, left, r - 1) + 1);
	};
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	string s;
	{
		Solution sln;
		s = "zzazz";
		auto res = sln.minInsertions(s);
		Assert(0, res);
	}

	{
		Solution sln;
		s = "mbadm";
		auto res = sln.minInsertions(s);
		Assert(2, res);
	}

	{
		Solution sln;
		s = "leetcode";
		auto res = sln.minInsertions(s);
		Assert(5, res);
	}
}

2023年2月第一版

class Solution {
public:
int minInsertions(string s) {
return s.length() - MaxNum(s);
}
int MaxNum(string s)
{
int c = s.length();
vector<vector> dp(c+1, vector©);
for (int j = 0; j < c; j++)
{
dp[1][j] = 1;
}
for (int len = 2; len <= c; len++)
{
for (int i = 0; i + len <= c; i++)
{
dp[len][i] = max(dp[len-1][i] ,dp[len-1][i+1]);
if (s[i] == s[i + len - 1])
{
dp[len][i] = max(dp[len][i], 2 + dp[len - 2][i + 1]);
}
}
}
return dp[c][0];
}
};

2023年2月第二版

class Solution {
public:
int minInsertions(string s) {
string strInv(s.rbegin(), s.rend());
return s.length() - longestCommonSubsequence(s, strInv);
}
int longestCommonSubsequence(string text1, string text2) {
vector pre(text1.size()+1);
for (int i = 1; i <= text2.length(); i++)
{
vector dp(text1.size() + 1);
for (int j = 1; j <= text1.size();j++ )
{
dp[j] = max(pre[j], dp[j - 1]);
if (text2[i - 1] == text1[j - 1])
{
dp[j] = max(dp[j], pre[j - 1]+1);
}
}
pre.swap(dp);
}
return pre.back();
}
};

2023年7月版

class Solution {
public:
int minInsertions(string s) {
for (int i = 0; i <= s.length(); i++)
{
for (int j = 0; j <= s.length(); j++)
{
m_result[i][j] = -1;
}
}
return minInsertions(s, 0, s.length());
}
//左闭右开
int minInsertions(const string& s, int left, int r)
{
if (r - left <= 1)
{
return 0;
}
int& result = m_result[left][r];
if (-1 != result)
{
return result;
}
if (s[left] == s[r - 1])
{
return result =minInsertions(s, left + 1, r - 1);
}
return result = 1 + min(minInsertions(s, left + 1, r), minInsertions(s, left, r - 1));
}
int m_result[501][501];
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛