迈克索夫特 On Campus

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问下楼主，这道题除了暴力方法以外还可以用什么方法呢？

宛若晨昏 发表于 2018-9-27 05:22
请问下楼主，这道题除了暴力方法以外还可以用什么方法呢？

对字符串翻转，然后用原串在翻转之后的串中做kmp

感谢！！

public String shortestPalindrome(String s) {
        String str = s + "#" + new StringBuilder(s).reverse().toString();
        int[]next = getNext(str);
        return new StringBuilder(s.substring(next[next.length - 1] + 1)).reverse().toString() + s;
    }
   
   
    public int[] getNext(String s){
        int[]next = new int[s.length()];
        int j = 0;
        int k = -1;
        next[0] = -1;
        while (j < s.length() - 1){
            if (k == -1 || s.charAt(j) == s.charAt(k)){
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }