LeetCode問題解(0214):文字列の前に文字を追加することによって回文列の最短回文列(Python)となる

テーマ:原題リンク(困難)
ラベル:文字列、二重ポインタ、再帰、KMPアルゴリズム
解法
時間の複雑さ
くうかんふくざつさ
実行時間
Ans 1 (Python)
O ( N 2 ) O(N^2) O(N2)
O ( N ) O(N) O(N)
464ms (23.10%)
Ans 2 (Python)
O ( N 2 ) O(N^2) O(N2)
O ( N ) O(N) O(N)
44ms (98.78%)
Ans 3 (Python)
O ( N ) O(N) O(N)
O ( N ) O(N) O(N)
56ms (92.39%)
この問題は、文字列の中で一番長い文字列を探すことに相当します.
解法一(暴力解法):

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        N = len(s)
        for i in range(N, 0, -1):
            if s[:i] == s[:i][::-1]:
                return s[i:][::-1] + s[:i] + s[i:]
        return ""

解法2(二重ポインタ再帰):
最悪の場合の時間的複雑度は変わらなかったが,平均的な場合の時間的複雑度は著しく低下した.

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        N = len(s)
        idx1 = 0
        for idx2 in range(N - 1, -1, -1):
            if s[idx1] == s[idx2]:
                idx1 += 1
        if idx1 == N:
            return s
        return s[idx1:][::-1] + self.shortestPalindrome(s[:idx1]) + s[idx1:]

解法三(KMPアルゴリズム):
KMPアルゴリズムの概要

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        s_new = s + "#" + s[::-1]
        N = len(s_new)

        table = [0] * N  # KMP    
        length = 0  #          
        i = 1  #     
        while i < N:
            if s_new[length] == s_new[i]:
                length += 1
                table[i] = length
                i += 1
            else:
                if length > 0:
                    length = table[length - 1]
                else:
                    i += 1
                    length = 0

        return s[table[-1]:][::-1] + s