新1站网站建设,wordpress邀请有奖,什么专业就业前景好,1688网站怎么做输入#xff1a;一个字符串s 输出#xff1a;最长的回文子串 规则#xff1a;“abba是一个回文 分析#xff1a;输入是babad”#xff0c;输出bab。这个问题不能再按照之前分段的思路解决#xff0c;或者说完全按照之前的思路。
之前的思路是一个字符串s 输出最长的回文子串 规则“abba是一个回文 分析输入是babad”输出bab。这个问题不能再按照之前分段的思路解决或者说完全按照之前的思路。
之前的思路是如果字符串只包含b只包含ba只包含bab…
因为要判断回文是要有以某个点为圆心的思想。最直观的感觉是从中间位置n/2开始判断。但思路没有进行下去。
如果已知aba是一个回文那么babab也是一个回文。这是dp的核心逻辑。(怎么找到这个逻辑?) 令dp[i][j]true,如果字符串从i到j是一个回文dp[i][j]true,如果字符串从i到j是一个回文dp[i][j]true,如果字符串从i到j是一个回文dp[i][j]false,如果字符串从i到j不是一个回文dp[i][j]false,如果字符串从i到j不是一个回文dp[i][j]false,如果字符串从i到j不是一个回文 如果s[i]s[j]并且dp[i1][j−1]trues[i]s[j]并且dp[i1][j-1]trues[i]s[j]并且dp[i1][j−1]true那么dp[i][j]truedp[i][j]truedp[i][j]true 基本情况是dp[i][i]truedp[i][i]truedp[i][i]true单个元素是回文dp[i][i1]true,当s[i]s[i1]dp[i][i1]true,当s[i]s[i1]dp[i][i1]true,当s[i]s[i1]相邻元素相同。 吐槽一般动态方程都是从dp[i-1]到dp[i]怎么会想到可以从dp[i1]到dp[i]。 这段代码编写也会是难点。 public String longestPalindrome(String s) {if(snull || s.length()0) return s;int n s.length();boolean[][] dp new boolean[n][n];int maxlen 1;int start 0;for(int i0;in;i){dp[i][i] true;if(in-1 s.charAt(i)s.charAt(i1)){dp[i][i1]true;start i;maxlen2;}}for(int j2;jn;j){for(int i0;ij;i){if(dp[i1][j-1] s.charAt(i) s.charAt(j)){dp[i][j]true;if(j-i1maxlen){maxlen j-i1;start i;}}}}return s.substring(start,startmaxlen);}分析2仍然是一种以某个点为中心的思想一个回文字符串中心的点可能是一个也可能是两个。会有2n-1个中心点。 例如babad。 以b为中心ba为中心 以a为中心以ab为中心 以b第2位为中心以ba为中心 … 直到结束 public String longestPalindrome(String s) {if(snull || s.length()0) return s;int start 0;int maxLen 1;for(int i0;is.length();i){int len1 expandAroundCenter(s,i,i);int len2 expandAroundCenter(s,i,i1);int len Math.max(len1,len2);if(lenmaxLen){start i - (len-1)/2;maxLen len;}}return s.substring(start,startmaxLen);}private int expandAroundCenter(String s ,int left,int right){while(left0 rights.length() s.charAt(left)s.charAt(right)){left--;right;}return right-left -1;}分析3Manacher 算法
public String longestPalindrome(String s) {if(snull || s.length()0) return s;char splitChar #;String str changeString(s,splitChar);int n str.length();int[] dp new int[n];int max 1;int middel 1;for(int i1;in;i){int step 0;int l i-1;int r i1;while(l0 rn str.charAt(l)str.charAt(r)){l--;r;step;}dp[i] step;if(stepmax){max step;middel i;}}int start (middel - max)/2; return s.substring(start,startmax);}private String changeString(String s,char splitChar){StringBuilder str new StringBuilder();str.append(splitChar);for(int i0;is.length();i){str.append(s.charAt(i));str.append(splitChar);}return str.toString();}参考文章link link
