主要锻炼的就是动态规划的思想!!!
掌握这种思想,工作中不一定用得上,但是多一种思想就多一种可能。
string longestPalindrome(string s)
{
int len = s.size();
if (len == 0 || len == 1)
return s;
int start = 0;
int maxLen = 1;
vector<vector<int>> dp(len, vector<int>(len));
for (int i = 0; i<len; i++)
{
dp[i][i] = 1;
if ( i < len - 1 && s[i] == s[i + 1])
{
dp[i][i + 1] = 1;
maxLen = 2;
start = i;
}
}
for (int subStrLen = 3; subStrLen <= len; subStrLen++)
{
for (int i = 0; i + subStrLen - 1<len; i++)
{
int j = subStrLen + i - 1;
if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
{
dp[i][j] = 1;
start = i;
maxLen = subStrLen;
}
}
}
return s.substr(start, maxLen);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)