LeetCode5.最长回文子串数据结构与算法冢狐的私人空间-

LeetCode5.最长回文子串

问题

分析

解法一：中心扩散法

• 顾名思义就是每一个位置中心去扩散，去找回文串，遇到不是回文串的时候结束。
• 寻找方法就是首先先找其左边和右边位置，如果相等即继续走，只到走到左边的值和右边的值都不和中间元素相等，然后判断左右值是否相等。

解法二：动态规划

​ 回看中心扩展算法，其实中间做了很多重复的计算，而动态规划就是为了减少重复计算的问题。即以空间换时间，将计算结果暂时存放起来，以避免重复计算

使用boolean dp[l] [r]表示字符串l到r这段是否是回文串，如果dp[l] [r]=true我们要判断dp[l-1] [r+1]是否是回文串只需要判断l-1和r+1两个位置的字符是否相同 

• 关键是找到初始状态以及状态转移方程
  • 初始状态：l=r此时dp[l] [r]=true
  • 状态转移方程：dp[l] [r]=true并且（l-1）和（r+1）两个位置为相同的字符，此时dp[l-1] [r+1]=true

解法三：马拉车算法

​ 马拉车算法本质上还是中心扩散法，只不过它使用了类似kmp算法的技巧，充分挖掘了已经镜像回文判定的子串的特点。在遍历的过程中，记录了已经遍历过的子串的信息。典型的以空间换时间。

对原始字符串进行预处理（添加分隔符）

• 即加入特殊字符，使得不用讨论奇偶情况，全是奇数情况。
• 新字符串的回文子串一定以分隔符作为两边的边界。

计算辅助数组p

​ 辅助数组p记录了新字符串中以每个字符为中心的回文子串的信息，辅助数组p的对大致就是”最长回文子串“的长度。

​ 另外在计算辅助数组p的过程中记录这个最大值。

代码实现

解法一：中心扩散法

 public static String longestPalindrome(String s) { if(s.length()<2){ return s; } int slen=s.length(); int ans=0; int len=1; int low=0; int heigh=0; int ansStart=0; for(int i=1;i<slen;i++){             len=1;             low=i-1;             heigh=i+1; while (low>=0&&s.charAt(low)==s.charAt(i)){                 len++;                 low--; } while (heigh<slen&&s.charAt(heigh)==s.charAt(i)){                 len++;                 heigh++; } while (low>=0&&heigh<slen&&s.charAt(low)==s.charAt(heigh)){                 len+=2;                 low--;                 heigh++; } if(len>ans){                 ans=len;                 ansStart=low; } } return s.substring(ansStart+1,ansStart+ans+1); } 

解法二：动态规划

public String longestPalindrome(String s) { if (s == null || s.length() < 2) { return s; } int strLen = s.length(); int maxStart = 0; //最长回文串的起点 int maxEnd = 0; //最长回文串的终点 int maxLen = 1; //最长回文串的长度 boolean[][] dp = new boolean[strLen][strLen]; for (int r = 1; r < strLen; r++) { for (int l = 0; l < r; l++) { if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {                     dp[l][r] = true; if (r - l + 1 > maxLen) {                         maxLen = r - l + 1;                         maxStart = l;                         maxEnd = r; } } } } return s.substring(maxStart, maxEnd + 1); } 

解法三：马拉车算法

   }     return s.substring(maxStart, maxEnd + 1);  }