开一个网站需要什么,网站建设人才有哪些,网站文案优化,鹤壁网站seo最长回文字串 1.问题描述2.中心扩展法#xff08;O(N^2)#xff09;3.动态规划4.Manacher(马拉车算法) 1.问题描述 常用有3种算法#xff1a;中心扩展法、动态规划和Manacher算法
2.中心扩展法#xff08;O(N^2)#xff09;
解释#xff1a; 从中心向外扩展。 分为两种… 最长回文字串 1.问题描述2.中心扩展法O(N^2)3.动态规划4.Manacher(马拉车算法) 1.问题描述 常用有3种算法中心扩展法、动态规划和Manacher算法
2.中心扩展法O(N^2)
解释 从中心向外扩展。 分为两种情况第一种当回文串长度为奇数的情况第二种当回文串长度为偶数的情况。 左右同时向外扩展当左右不相同时停止扩展记录最长回文串长度及起始位置。 public String longestPalindrome(String str) {if (Objects.isNull(str) || str.isEmpty()) {return ;}int maxStart 0;int maxLength 1;for (int i 0; i str.length(); i) {for (int k 0; k 2; k) {int leftIndex i - k; // k 0表示偶数长度k 1表示奇数长度int rightIndex i 1;while (leftIndex 0 rightIndex str.length() str.charAt(leftIndex) str.charAt(rightIndex)) {leftIndex--;rightIndex;}if (maxLength rightIndex - leftIndex - 1) { // 当前length (rightIndex - 1) - (leftIndex 1) 1maxLength rightIndex - leftIndex - 1;maxStart leftIndex 1;}}}return str.substring(maxStart, maxStart maxLength);} 3.动态规划
4.Manacher(马拉车算法)
