电商网站规划设计方案,seo实战密码在线阅读,本地wordpress卸载,上海商城网站题目
给定一个字符串 s#xff0c;你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1#xff1a; 输入#xff1a;s “aacecaaa” 输出#xff1a;“aaacecaaa” 示例 2#xff1a;
输入#xff1a;s “abcd” 输…题目
给定一个字符串 s你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 示例 1 输入s “aacecaaa” 输出“aaacecaaa” 示例 2
输入s “abcd” 输出“dcbabcd”
提示 0 s.length 5 * 104 s 仅由小写英文字母组成
分析
我们可以将s分成两部分s1s2其中s1是回文假定前面增加的字符串是s0。因为s0s1s2是回文所以s0和s2是逆序。要想s0最短就要s2最短,也就是s1最长。那么此题的本质就是求s是回文的最长前缀。如果s不存在回文前缀则认为s1为空。求出s1后再求s0和s2并返回s0s1s2。 求回文至少有两种办法一枚举回文中心时间复杂度O(n^2)。本题会超时。二马拉车算法时间复杂度O(n)。比较复杂过些天专门写篇博文介绍马拉车算法。建议将马拉车算法封装成类。
2023年4月版
class Solution { public: string shortestPalindrome(string s) { if (“” s) { return “”; } m_c s.length(); std::string s1 Do(s); std::string strAdd; for (int i s.length() - 1; i s1.length(); i–) { strAdd s[i]; } return strAdd s; } string Do(const string s) { vector next(m_c, -1); for (int i 1; i m_c; i) { int iNext next[i - 1]; while ((-1 ! iNext) (s[iNext 1] ! s[i])) { iNext next[iNext]; } next[i] (s[i] s[iNext 1]) ? iNext 1 : iNext; } std::string sRever(s.rbegin(), s.rend()); int i 0, j 0; while ((im_c)(jm_c)) { while ((i m_c) (j m_c) (s[i] sRever[j])) { i; j; } if (i m_c - (j - i)) { return s.substr(0, i); } if (j m_c) { return “”; } if ((i 0) (next[i - 1] 0)) { i next[i - 1] 1; } else { if (i 0) { i 0; } else { j; } } } return s.substr(0,1); } int m_c; };
2023年8月版马拉车
class CKMP { public: static vector Next(const string s) { const int len s.length(); vector vNext(len, -1); for (int i 1; i len; i) { int next vNext[i - 1]; while ((-1 ! next) (s[next 1] ! s[i])) { next vNext[next]; } vNext[i] next (s[next 1] s[i]); } return vNext; } }; class Solution { public: string shortestPalindrome(string s) { vector next CKMP::Next(s); int n s.length(); int preSameIndex -1; for (int i n - 1; i 0; i–) { const auto ch s[i]; while ((-1 ! preSameIndex) (s[preSameIndex 1] ! ch)) { preSameIndex next[preSameIndex]; } if (ch s[preSameIndex 1]) { preSameIndex; } } string add (preSameIndex n - 1 ? “” : s.substr(preSameIndex 1, n)); reverse(add.begin(), add.end()); return add s;
}}; 其它
视频课程
如果你觉得复杂想从简单的算法开始可以学习我的视频课程。 https://edu.csdn.net/course/detail/38771
我的其它课程 https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C17
相关下载
算法精讲《闻缺陷则喜算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
作者人生格言有所得以墨记之故曰墨家闻缺陷则喜。问题发现得越早越给老板省钱。算法是程序的灵魂
