免费看国产黄色,国产毛片18水真多18精品,无码导航,www.韩国三级,免费观看操美女,欧美日韩一级A片,可以赌博看毛片的网站,在线国产激情视频

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做 最短回文串，我們先來(lái)看題面：

https://leetcode-cn.com/problems/shortest-palindrome/

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

題意

給定一個(gè)字符串 s，你可以通過(guò)在字符串前面添加字符將其轉(zhuǎn)換為回文串。找到并返回可以用這種方式轉(zhuǎn)換的最短回文串。

示例

示例 1：

輸入：s = "aacecaaa"
輸出："aaacecaaa"

示例 2：

輸入：s = "abcd"
輸出："dcbabcd"
 
提示：

0 <= s.length <= 5 * 104
s 僅由小寫英文字母組成

解題

https://blog.csdn.net/qq_41231926/article/details/86747126

思路一：暴力破解法

要找到滿足題目要求的最短回文串，本質(zhì)是要找到最長(zhǎng)的回文子串，該子串的左端點(diǎn)與字符串s的左端點(diǎn)重合。

時(shí)間復(fù)雜度是O(n ^ 2)，其中n為字符串s的長(zhǎng)度?？臻g復(fù)雜度是O(n)。

JAVA代碼：

class Solution {
    public String shortestPalindrome(String s) {
        int index = -1;
        for(int i = s.length() - 1; i >= 0; i--){
            if(isPalindrome(s.substring(0, i + 1))){
                index = i;
                break;
            }
        }
        String result = reverse(s.substring(index + 1));
        return result + s;
    }
    private String reverse(String s){
        StringBuilder stringBuilder = new StringBuilder(s);
        return stringBuilder.reverse().toString();
    }
    private boolean isPalindrome(String s){
        for(int i = 0; i < s.length() / 2; i++){
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}

思路二：遞歸解法

左指針i初始化為0，右指針j從n - 1遞減到0，其中n為字符串s的長(zhǎng)度，一旦遇上i指向的字符與j指向的字符相等時(shí)，令i指針加1。

遞歸出口：

如果i指針最后的值等于n，說(shuō)明字符串s本身就是回文串，直接返回s即可。

遞歸過(guò)程：

首先明確一點(diǎn)：我們所要尋找的最長(zhǎng)回文子串，該子串的左端點(diǎn)與字符串s的左端點(diǎn)重合，一定在[0, i)范圍內(nèi)。

考慮兩種極端情況，第一種情況：字符串s本身就是回文串，顯然滿足條件。第二種情況：在遍歷過(guò)程中，不存在i指向的字符與j指向的字符相等的情況，除了i和j相等時(shí)，這種情況我們得到的i是1。顯然也滿足條件。

考慮一般性情況：假設(shè)我們所要尋找的最長(zhǎng)回文子串不在[0, i)范圍內(nèi)，即存在回文串其在[0, k)范圍內(nèi)，其中k > i。那么顯然，在我們遍歷的過(guò)程中，即使j在[k, n - 1]范圍時(shí)不存在i指向的字符與j指向的字符相等的情況，最終i的值也會(huì)到達(dá)k，即i >= k，這顯然矛盾了，因此該結(jié)論成立。

由上述結(jié)論，我們得出：[i, n - 1]范圍內(nèi)的子串一定不是我們所要尋找的最長(zhǎng)回文子串的一部分。

這樣，我們就可以遞歸地反轉(zhuǎn)[0, i)范圍內(nèi)的子串來(lái)拼接出結(jié)果。

時(shí)間復(fù)雜度是O(n ^ 2)，其中n為字符串s的長(zhǎng)度?？臻g復(fù)雜度是O(n)。

JAVA代碼：

class Solution {
    public String shortestPalindrome(String s) {
        int i = 0;
        for(int j = s.length() - 1; j >= 0; j--){
            if(s.charAt(j) == s.charAt(i)){
                i++;
            }
        }
        if(i == s.length()){
            return s;
        }
        return reverse(s.substring(i)) + shortestPalindrome(s.substring(0, i)) + s.substring(i);
    }
    private String reverse(String s){
        StringBuilder stringBuilder = new StringBuilder(s);
        return stringBuilder.reverse().toString();
    }
}

思路三：KMP算法

將原字符串s和其逆序字符串用“#”拼接在一起，利用KMP算法中next數(shù)組的求法求得拼接出的新字符串的最長(zhǎng)相同前后綴，就是原字符串s中最長(zhǎng)的回文子串，該子串的左端點(diǎn)與字符串s的左端點(diǎn)重合。

這個(gè)問(wèn)題是一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題：求取字符串s中的最長(zhǎng)相同前后綴（不能是其本身）

狀態(tài)定義：

f(x) -------- 字符串s中[0, x]范圍內(nèi)的最長(zhǎng)相同前后綴（不能是其本身）的長(zhǎng)度

狀態(tài)轉(zhuǎn)移：

首先是初始化，f(0)顯然是0，因?yàn)閇0, 0]范圍內(nèi)的字符串長(zhǎng)度為1，其最長(zhǎng)相同前后綴根本不存在。

對(duì)于i在[1, n - 1]（其中n為字符串s的長(zhǎng)度）范圍內(nèi)的值：

（1）令temp記錄f(x - 1)的值，如果temp大于0且s中temp位置的字符和第i個(gè)字符不相同，那么我們就需要重設(shè)temp的值為f(temp - 1)。

（2）如果s中第i個(gè)字符與第temp個(gè)字符相同，令temp自增1。

（3）f(i) = temp。

上述狀態(tài)轉(zhuǎn)移過(guò)程可能很難理解，以一個(gè)例子——“ABABCABAA”來(lái)說(shuō)明，其子串如下：

A -------------------------------------------------- 0

AB ------------------------------------------------ 0

ABA ---------------------------------------------- 1

ABAB -------------------------------------------- 2

ABABC ------------------------------------------ 0

ABABCA ---------------------------------------- 1

ABABCAB -------------------------------------- 2

ABABCABA ------------------------------------ 3

ABABCABAA ---------------------------------- 1

對(duì)由ABAB求得ABABC這個(gè)過(guò)程進(jìn)行分析：

C和A不相等，因此結(jié)果不可能是3，如果是ABABA，則結(jié)果是3。ABAB的結(jié)果是2，因此我們知道AB和AB相同，但是第一個(gè)AB之后跟著的是A，依然和C不相同。我們繼續(xù)看AB，AB的結(jié)果是0，因此我們知道AB中A和B不相同，而C和A不相同，因此結(jié)果是0。

對(duì)由ABABCABA求得ABABCABAA這個(gè)過(guò)程進(jìn)行分析：

A和B不相等，因此結(jié)果不可能是4，如果是ABABCABAB，則結(jié)果是4。ABABCABA的結(jié)果是3，因此我們知道ABA和ABA相同，但是第一個(gè)ABA之后跟著的是B，依然和A不相同。我們繼續(xù)看ABA，ABA的結(jié)果是1，但是第一個(gè)A之后跟著的是B，依然和A不相同。我們繼續(xù)看A，結(jié)果是0，結(jié)束while循環(huán)。這個(gè)A和A相同，因此其值加1變成1。

時(shí)間復(fù)雜度和空間復(fù)雜度均是O(n)，其中n為字符串s的長(zhǎng)度。

JAVA代碼：

class Solution {
    public String shortestPalindrome(String s) {
        String rev = reverse(s);
        String temp = s + "#" + rev;
        int[] next = getNext(temp);
        return rev.substring(0, rev.length() - next[temp.length() - 1]) + s;
    }
    private String reverse(String s){
        StringBuilder stringBuilder = new StringBuilder(s);
        return stringBuilder.reverse().toString();
    }
    private int[] getNext(String s){
        int[] result = new int[s.length()];
        result[0] = 0;
        for(int i = 1; i < result.length; i++){
            int temp = result[i - 1];
            while(temp > 0 && s.charAt(i) != s.charAt(temp)){
                temp = result[temp - 1];
            }
            if(s.charAt(i) == s.charAt(temp)){
                temp++;
            }
            result[i] = temp;
        }
        return result;
    }
}