214. 最短回文串
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
class Solution { public static String shortestPalindrome(String s) { StringBuilder r = new StringBuilder(s).reverse(); String str = s + "#" + r; int[] next = next(str); //如果是回文串 # //next[str.length]=7,r.substring(0,0)=""输出原字符串 //如果 # next[str.length]=5 //r.substring(0,6-5),只需要第一位 String prefix = r.substring(0, r.length() - next[str.length()]); return prefix + s; } // next数组 //KMP的next[j]=x就是0~x-1与 j-x~j-1 的元素是相同的 //大概是这样 private static int[] next(String P) { int[] next = new int[P.length() + 1]; next[0] = -1; int k = -1; int i = 1; //next【k】保存的是我上次相等的时候 //不相等的时候我就从我上一次相等的时候就行匹配 //i是快指针，k是慢指针 while (i < next.length) { if (k == -1 || P.charAt(k) == P.charAt(i - 1)) { next[i++] = ++k; } else { k = next[k]; } } return next; } } 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/225422.html原文链接：https://javaforall.net
