leetcode 5. 最长回文子串

leetcode 5. 最长回文子串

leetcode [​​5. 最长回文子串​​](​​s​​​，找到 ​​s​​ 中最长的回文子串。

动态规划法求解最大回文串。

class Solution {public: string longestPalindrome(string s) { bool dp[1005][1005]; //存储状态 int len = s.length(),ans = 1,from = 0; for(int i = 0;i < len;++i) //状态初始化 dp[i][i] = true; for(int i = 0,j = len - 1;i < j;++i) if(s[i] == s[i + 1]) dp[i][i + 1] = true,ans = 2,from = i; else dp[i][i + 1] = false; for(int i = 2,j = len;i < j;++i) //状态方程 for(int p = 0,q = len - i;p < q;++p) if(s[p] == s[p + i]){ if(dp[p + 1][p + i - 1]) dp[p][p + i] = true,ans = i + 1,from = p; else dp[p][p + i] = false; } else dp[p][p + i] = false; return s.substr(from,ans); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。