【最长公共前缀 动态规划】2430. 对字母串可执行的最大删除数

如果有不明白的，请加文末QQ群。

本文涉及知识点

最长公共前缀 动态规划

动态规划汇总

LeetCode 2430. 对字母串可执行的最大删除数

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：

删除 整个字符串 s ，或者

对于满足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。

例如，如果 s = “ababc” ，那么在一步操作中，你可以删除 s 的前两个字母得到 “abc” ，因为 s 的前两个字母和接下来的两个字母都等于 “ab” 。

返回删除 s 所需的最大操作数。

示例 1：

输入：s = “abcabcdabc”

输出：2

解释：

• 删除前 3 个字母（“abc”），因为它们和接下来 3 个字母相等。现在，s = “abcdabc”。
• 删除全部字母。

  一共用了 2 步操作，所以返回 2 。可以证明 2 是所需的最大操作数。

  注意，在第二步操作中无法再次删除 “abc” ，因为 “abc” 的下一次出现并不是位于接下来的 3 个字母。

  示例 2：

  输入：s = “aaabaab”

  输出：4

  解释：

• 删除第一个字母（“a”），因为它和接下来的字母相等。现在，s = “aabaab”。
• 删除前 3 个字母（“aab”），因为它们和接下来 3 个字母相等。现在，s = “aab”。
• 删除第一个字母（“a”），因为它和接下来的字母相等。现在，s = “ab”。
• 删除全部字母。

  一共用了 4 步操作，所以返回 4 。可以证明 4 是所需的最大操作数。

  示例 3：

  输入：s = “aaaaa”

  输出：5

  解释：在每一步操作中，都可以仅删除 s 的第一个字母。

  提示：

  1 <= s.length <= 4000

  s 仅由小写英文字母组成

  最长公共前缀

  n = s.length

  先预处理出最长公共前缀lcp，时间复杂度：O(nn)。

  动态规划的状态表示

  dp[i]记录 s[i… ]的最大操作次数。空间复杂度: O(n)

  动态规划的填表顺序

  dp[i] = 1

  for(len =1 ; i+len*2 <=n ;len++)

  如果lcp[i][i+len] >= len 则 dp[i] = max(dp[i],dp[i+len]+1);

  单个状态转移的时间复杂度：O(n)

  总时间复杂度：O(nn)

  动态规划的初始值

  全为1

  动态规划的填表顺序

  i = n -1 to 0

  动态规划的返回值

  dp[0]

  代码

  核心代码

  //最长公共前缀(Longest Common Prefix)
  class CLCP
  {public:
  	CLCP(const string& str1, const string& str2)
  	{m_dp.assign(str1.length() , vector(str2.length()));
  		//str1[j...)和str2[k...]比较时, j和k不断自增，总有一个先到达末端
  		for (int i = 0; i < str1.length(); i++)
  		{//枚举str2 先到末端 str1[i]和str2.back对应
  			m_dp[i][str2.length() - 1] = (str1[i] == str2.back());
  			for (int j = i-1 ; j >= 0 ; j-- )
  			{const int k = str2.length() - 1 - (i-j);
  				if (k < 0)
  				{break;
  				}
  				if (str1[j] == str2[k])
  				{m_dp[j][k] = 1 + m_dp[j + 1][k + 1];
  				}
  			}			
  		}
  		for (int i = 0; i < str2.length(); i++)
  		{//枚举str1 先到末端 str2[i]和str1.back对应
  			m_dp[str1.length()-1][i] = (str1.back() == str2[i]);
  			for (int j = i - 1; j >= 0; j--)
  			{const int k = str1.length() - 1 - (i-j);
  				if (k < 0)
  				{break;
  				}
  				if (str1[k] == str2[j])
  				{m_dp[k][j] = 1 + m_dp[k + 1][j + 1];
  				}
  			}
  		}
  	}
  	vector> m_dp;
  };
  templatevoid MaxSelf(ELE* seft, const ELE& other)
  {*seft = max(*seft, other);
  }
  class Solution {public:
  	int deleteString(string s) {CLCP lcp(s, s);
  		vector dp(s.length(), 1);
  		for (int i = s.length() - 1; i >= 0; i--) {for (int len = 1; i + len * 2 <= s.length(); len++) {if (lcp.m_dp[i][i + len] >= len) {MaxSelf(&dp[i], dp[i + len] + 1);
  				}
  			}
  		}
  		return dp.front();
  	}
  };
  

  单元测试

  templatevoid AssertEx(const T1& t1, const T2& t2)
  {Assert::AreEqual(t1, t2);
  }
  templatevoid AssertEx(const vector& v1, const vector& v2)
  {Assert::AreEqual(v1.size(), v2.size());
  	for (int i = 0; i < v1.size(); i++)
  	{Assert::AreEqual(v1[i], v2[i]);
  	}
  }
  templatevoid AssertV2(vector> vv1, vector> 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
  {string s;
  	TEST_CLASS(UnitTest)
  	{public:
  		TEST_METHOD(TestMethod00)
  		{s = "abcabcdabc";
  			auto res = Solution().deleteString(s);
  			AssertEx(2, res);
  		}
  		TEST_METHOD(TestMethod01)
  		{s = "aaabaab";
  			auto res = Solution().deleteString(s);
  			AssertEx(4, res);
  		}
  		TEST_METHOD(TestMethod02)
  		{s = "aaaaa";
  			auto res = Solution().deleteString(s);
  			AssertEx(5, res);
  		}
  	};
  }
  

  扩展阅读

  视频课程

  先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

  https://edu.csdn.net/course/detail/38771

  如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

  https://edu.csdn.net/lecturer/6176

  相关推荐

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

  测试环境

  操作系统：win7 开发环境： VS2019 C++17

  或者 操作系统：win10 开发环境： VS2022 C++17

  如无特殊说明，本算法用**C++**实现。