214. Shortest Palindrome

beita 发布于2019-08-16 10:29 / 1460人阅读

摘要：题目链接找到从头开始最长的那么只要把的加到前面就是结果了。找的过程可以用来做优化，由于，那么就照着里面见数组的方法来查，最后就是的长度，注意两个并在一起的要加分隔符，防止算的出问题。

214. Shortest Palindrome

题目链接：https://leetcode.com/problems...

找到string从头开始最长的palindrome substring：s[0:i+1]
那么只要把substring(i+1)的reverse加到s前面就是结果了。
找palindrome substring的过程可以用kmp来做优化，由于reverse(s[0:i+1]) == s[0:i+1]，那么就照着kmp里面见prefix数组的方法来查，最后prefix[n-1]就是palindrome的长度，注意两个string并在一起的要加分隔符，防止算prefix的出问题。

public class Solution {
    public String shortestPalindrome(String s) {
        StringBuilder rev = new StringBuilder(s).reverse();
        String d = s + "#" + rev.toString();
        int n = d.length();
        int[] prefix = new int[n];
        // i for rev, j for s
        int i = 1, j = 0;
        while(i < n) {
            // match
            if(d.charAt(j) == d.charAt(i)) {
                prefix[i] = j + 1;
                i++;  j++;
            }
            else {
                if(j == 0) i++;
                else j = prefix[j-1];
            }
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(s.substring(prefix[n-1]));
        return sb.reverse().append(s).toString();
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69888.html

[LeetCode] 214. Shortest Palindrome

Problem Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation. Exa...

liangdas 2019-08-16 13:56 评论0 收藏0
Palindrome Pairs & Shortest Palindrome

摘要：部分是回文的，在里面找是否有的。这里的范围是，最小是，因为要保证是两个单词，最大是，这时候要找出另一个和他相反的串。判断为回文，可以直接暴力，每个都判断一次。两个方向都找一遍就可能出现重复的情况，注意避免重复。例如，结果应该是。 Palindrome Pairs 链接：https://leetcode.com/problems... 这道题没想出来思路，参考了这个博客的内容：http:...

CNZPH 2019-08-14 17:20 评论0 收藏0
[Leetcode] Shortest Palindrome 最短回文拼接法

摘要：第二个是，因为在第个位置，可以有最长为的相同前后缀，依次类推。匹配时分为几种情况字母相同，则和都加，且，因为后缀匹配的长度是前缀的长度加。注意为了方便处理空字符串，我们在反转拼接的时候中间加了，这个字符要保证不会出现在字符串中。 Shortest Palindrome Given a string S, you are allowed to convert it to a palin...

Chiclaim 2019-08-14 12:37 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0