leetcode214. 最短回文串

214. 最短回文串

难度困难114

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

输入: "aacecaaa"
输出: "aaacecaaa"

 

示例 2:

输入: "abcd"
输出: "dcbabcd"
 

思路：马拉车求出以0开头的最大回文串，然后在前面添加后面字符串的翻转即可。

傻子都能看懂的马拉车Manacher

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public String preProcess(String s) {
     
    
   

    

     

    
    

     
 int n = s.length();
     
    
   

    

     

    
    

     
 if (n == 0) {
     
    
   

    

     

    
    

     
 return "^$";
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       String ret = "^";
     
    
   

    

     

    
    

     
 for (int i = 0; i < n; i++)
     
    
   

    

     

    
    

     

       ret += "#" + s.charAt(i);
     
    
   

    

     

    
    

     

       ret += "#$";
     
    
   

    

     

    
    

     
 return ret;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // 马拉车算法
     
    
   

    

     

    
    

     

      public String shortestPalindrome(String s) {
     
    
   

    

     

    
    

     

       String T = preProcess(s);
     
    
   

    

     

    
    

     
 int n = T.length();
     
    
   

    

     

    
    

     
 int[] P = new int[n];
     
    
   

    

     

    
    

     
 int C = 0, R = 0;
     
    
   

    

     

    
    

     
 for (int i = 1; i < n - 1; i++) {
     
    
   

    

     

    
    

     
 int i_mirror = 2 * C - i;
     
    
   

    

     

    
    

     
 if (R > i) {
     
    
   

    

     

    
    

     

       P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     

       P[i] = 0;// 等于 R 的情况
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 // 碰到之前讲的三种情况时候，需要利用中心扩展法
     
    
   

    

     

    
    

     
 while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
     
    
   

    

     

    
    

     

       P[i]++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 // 判断是否需要更新 R
     
    
   

    

     

    
    

     
 if (i + P[i] > R) {
     
    
   

    

     

    
    

     

       C = i;
     
    
   

    

     

    
    

     

       R = i + P[i];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 //这里的话需要修改
     
    
   

    

     

    
    

     
 int maxLen = 0;
     
    
   

    

     

    
    

     
 int centerIndex = 0;
     
    
   

    

     

    
    

     
 for (int i = 1; i < n - 1; i++) {
     
    
   

    

     

    
    

     
 int start = (i - P[i]) / 2;
     
    
   

    

     

    
    

     
 //我们要判断当前回文串是不是开头是不是从 0 开始的
     
    
   

    

     

    
    

     
 if (start == 0) {
     
    
   

    

     

    
    

     

       maxLen = P[i] > maxLen ? P[i] : maxLen;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return new StringBuilder(s.substring(maxLen)).reverse() + s;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104368047