如何注册属于自己的网站,网站关键词符号,怎么用手机做网站教程,青岛房产网签备案查询文章目录题目描述解法 代码#xff1a;思路题目描述
回文#xff1a;正着念和倒着念一样。
解法 代码#xff1a;
一开始看到子串#xff0c;想着可能no.3最长重复子串一样用滑动窗口。不过回文串的判断会很麻烦#xff0c;于是舍弃。之后看题解#xff…
文章目录题目描述解法 代码思路题目描述
回文正着念和倒着念一样。
解法 代码
一开始看到子串想着可能no.3最长重复子串一样用滑动窗口。不过回文串的判断会很麻烦于是舍弃。之后看题解用的是动态规划。
思路
从短串到长串循环最终得到一个dp[][]二维矩阵dp[i][j]代表S(i,j)是否是回文串。单个元素的情况必然是回文串。dp[i][i]。两个元素的情况根据S[i] S[i1]即可判断。多个元素的情况根据dp[i1][j-1]以及S[i] S[j]即可判断。有了这三种情况我们就有了状态转移方程。对于循环可以看成是对于每一个子串长度都从每一个左边界 i开始构成串因此j i的情况全算是false。
class Solution {public String longestPalindrome(String s) {// 用dp(Dynamic Programming)int len s.length();// 空间复杂度O(n*n)boolean[][] dp new boolean[len][len];String ans ;// 字串长度nowLenfor (int nowLen 0; nowLen len; nowLen) {// 字串左边界ifor (int i 0; i nowLen len; i) {// 字串右边界int j i nowLen;// 子串单个元素的情况if (nowLen 0) {dp[i][j] true;}// 子串两个元素的情况else if (nowLen 1) {dp[i][j] (s.charAt(i) s.charAt(j));}// 多个元素的情况用之前的结果构造当前结果else {dp[i][j] dp[i 1][j - 1] (s.charAt(i) s.charAt(j));}if (ans.length() j - i 1 dp[i][j]) {ans s.substring(i, j 1);}}}return ans;}
}时间复杂度O(n2n^2n2)因为动态规划的状态总数为n2n^2n2对于每一个状态进行转移的时间为O(1)空间复杂度O(n2n^2n2)也就是dp[n][n]存储动态规划状态需要的空间。
