本文涉及知识点
回文 马拉车
LeetCode214. 最短回文串
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入:s = “aacecaaa”
输出:“aaacecaaa”
示例 2:
输入:s = “abcd”
输出:“dcbabcd”
提示:
0 <= s.length <= 5 * 104
s 仅由小写英文字母组成
回文
n = s.length
将定在s前面增加了n1个字符,则增加的是字符串一定是s,长度为n1的后缀逆序。此时字符串是回文说明:s[0…n-n1-1]是回文。
此问题 ⟺ \iff ⟺ 求s的最长回文前缀。
先用马拉车算法计算,奇数长度回文的最大半长,看能否包括s[0],如果包括更新最大长度。
偶数长度回文类似。
代码
核心代码
//马拉车计算回文回文
class CPalindrome
{
public:void CalCenterHalfLen(const string& s){vector<char> v = { '*' };for (const auto& ch : s){v.emplace_back(ch);v.emplace_back('*');}const int len = v.size();vector<int> vHalfLen(len);int center = -1, r = -1;//center是对称中心,r是其右边界(闭)for (int i = 0; i < len; i++){int tmp = 1;if (i <= r){int pre = center - (i - center);tmp = min(vHalfLen[pre], r - i + 1);}for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);vHalfLen[i] = --tmp;const int iNewR = i + tmp - 1;if (iNewR > r){r = iNewR;center = i;}}m_vOddCenterHalfLen.resize(s.length());m_vEvenCenterHalfLen.resize(s.length());for (int i = 1; i < len; i++){const int center = (i - 1) / 2;const int iHalfLen = vHalfLen[i] / 2;if (i & 1){//原字符串奇数长度m_vOddCenterHalfLen[center] = iHalfLen;}else{m_vEvenCenterHalfLen[center] = iHalfLen;}}}vector<int> m_vOddCenterHalfLen, m_vEvenCenterHalfLen;//vOddHalfLen[i]表示 以s[i]为中心,且长度为奇数的最长回文的半长,包括s[i]//比如:"aba" vOddHalfLen[1]为2 "abba" vEvenHalfLen[1]为2
};template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}class Solution {
public:string shortestPalindrome(string s) {if ("" == s) { return ""; };CPalindrome pn;pn.CalCenterHalfLen(s);int iMaxR = 0;for (int i = 0; i < s.length(); i++) {int left = i - pn.m_vOddCenterHalfLen[i] + 1;int r = i + pn.m_vOddCenterHalfLen[i] - 1;if (0 == left) {MaxSelf(&iMaxR, r);}}for (int i = 0; i < s.length(); i++) {int left = i - pn.m_vEvenCenterHalfLen[i] + 1;int r = i + pn.m_vEvenCenterHalfLen[i] ;if (0 == left) {MaxSelf(&iMaxR, r);}}string s2 = s.substr(iMaxR + 1);return string(s2.rbegin(), s2.rend()) + s;}
};
单元测试
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
{string s;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){s = "aacecaaa";auto res = Solution().shortestPalindrome(s);AssertEx(string("aaacecaaa"), res);}TEST_METHOD(TestMethod1){s = "abcd";auto res = Solution().shortestPalindrome(s);AssertEx(string("dcbabcd"), res);}TEST_METHOD(TestMethod2){s = "ab";auto res = Solution().shortestPalindrome(s);AssertEx(string("bab"), res);}TEST_METHOD(TestMethod3){s = "aab";auto res = Solution().shortestPalindrome(s);AssertEx(string("baab"), res);}TEST_METHOD(TestMethod4){s = "";auto res = Solution().shortestPalindrome(s);AssertEx(string(""), 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++**实现。