Leetcode - 336. Palindrome Pairs

質問リンク:leetcode 336問題
質問:単語リストで、単語[i]+word[j]がフィリン症候群のすべてのインデックスの組み合わせ(i,j)になることを求めます.
草.(ブルテポス)
二つの言葉を合わせて、その言葉がフィリンドロムであることを確認します.

def palindromePairs(self, words):
        
        def check(word1,word2):
            word = word1 + word2

            if word == word[::-1]:
                return True
            else:
                return False
        
        result = []
    
        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue
                else:
                    if check(words[i],words[j]):
                       result.append([i,j])
        
        return result               

しかし結果はRuntime Errorであった.なんといってもO(n^2)の時間複雑度なので、ちょっと無理です.
では、どのような解答が適当なのでしょうか.
私が選んだのはテリーです.
trieを用いると,いずれにしても時間複雑度は検索する文字列の長さであるため,前述したbrootforceの時間複雑度問題を解決できる.
時間的複雑度がO(n)の場合に解くために,すべての入力値をtrieとし,一度だけ検索する問題に変換する.フィリンドロンを見分けたいので、入力した文字をひっくり返してトレイに詰めます.
入力値の例は、['d]、[cbcd]、[dcbb]、[dcdc]、[cbbc]、[bbcd]など、やや複雑な値を入力値として、下図のように反転しています.

反転した入力値を既存のtrieで実現(挿入)し,ピクチャとして提示する.
wはその単語を表し,隣の変数はアドレス値を表す.
したがって、これらのストライプ入力値によって、フィリンドロンかどうかを決定したいと考えています.では、フェリンドロンをどのように区別しますか?

1.ナビゲーション中にwがある場合

 while word:
            # node.word > -1이 있다는 뜻은 펠린드롬 될 수 있는 항목이 다른 입력값에 존재한다는 뜻
            if node.word_id > -1:
                # 그 나머지 입력값들이 펠린드롬이라면 그 수는 펠린드롬
                if self.isPalindrome(word):
                    #결과값에 인덱스와 해당 노드이 인덱스를 넣어준다.
                    result.append([index,node.word_id])
            
            if not word[0] in node.children:
                return result
            
            node = node.children[word[0]]
            word = word[1:]
	

反転していない単語を入力し、その単語にwマークがあれば、後ろの残りの文字がピンインかどうかを判断することでピンインかどうかを判断します.

入力値:['d'、'cbbcd'、'dcbb'、'dcbc'、'cbbbc'、'bbcd']の「dcbbc」を例に挙げます.
1)最初の値dが「dcbc」から取り出された場合.
2)dノードのw=0で表し、残りの文字にピンインがあるかどうかをチェックします.=>'cbcなのでフェリンドロンです.したがって、dcbc+dはペリン症候群である.

2.入力値=反転したストライプ

#순서대로 끝까지 탐색한 후 
#만약 node.word_id가 0보다 같거나 크고 index가 서로 다르다면(ex) "abcd", "dcba"와 같은)
if node.word_id >= 0 and node.word_id != index:
	result.append([index, node.word_id])

以前word[1:]文で入力値を1つずつ検索していたが,フィリンドロム値が見つかった.しかし、この過程で「abcd」やdcbaのようなフィリンドロンがなくても、フィリンドロンの入力値=反転となるトレは抽出できない.

前の入力値:['d'、'cbbcd'、'dcbb'、'dcbc'、'cbbbc'、'bbcd']の'bbcd'を例に挙げます.
以前は関数「dcbb」を挿入して反転して図中の赤いツリーを完成した.したがって,プローブ関数に「bbcd」と入力すると,ツリーの末尾(w>0)まで続くので,フィリンドロンと呼ぶ.

3.最後まで検索したときにpがあれば

p? 君はきっと驚いたに違いない.このpは前に関数を挿入したときに加えたものではありません.
ではpは何でしょうか.前に挿入関数に入力した単語を逆さにして入れます.各単語をツリーに置くと、残りの部分がフェリンドロムであれば、ノートを通じて対応するノードにP値を格納します.図に示すように

では、この注釈でどのようなフィリンドロムが見つかるか見てみましょう.
前の入力値:['d]、[cbbcd]、[dcbb]、[dcbc]、[cbbc]、[bcd]]の「dcbb」.

入力値dcbbの最後のノードはp=1である.すなわち、dcbb+c(注釈バージョン)+bcdによりフィリン症候群となる.
では、ルートストレージのp=0、p=4とは何でしょうか.
気づいた人もいるかもしれませんが、それは元の入力値がフィリンドロムです.
コードは次のとおりです.

# 2 : 펠린드롬값 + 입력값 찾기
# 끝까지 탐색했을 때 그 노드에 펠린드롬 표시가 있다면 그 단어는 펠린드롬이다. 
for p in node.palindrome:
    result.append([index,p])

完全なコード
wはword id
pはpayldromeリストとして表される.

class Node:
    def __init__(self,key):
        self.key = key
        self.palindrome = []
        self.word_id = -1
        self.children = {}

class Trie(object):
    def __init__(self):
        self.root = Node(None)

    @staticmethod
    def isPalindrome(word):
        return word[::] == word[::-1]

    def insert(self, index, word):
        node = self.root

        for i, ch in enumerate(reversed(word)):
            if self.isPalindrome(word[:len(word)-i]):
                node.palindrome.append(index)
            
            if ch not in node.children:
                node.children[ch] = Node(ch)

            node = node.children[ch]    

        node.word_id = index       

    def search(self, index, word):
        node = self.root

        result = []

        while word:
            if node.word_id > -1:
                if self.isPalindrome(word):
                    result.append([index,node.word_id])
            if not word[0] in node.children:
                return result
            
            node = node.children[word[0]]
            word = word[1:]

        if node.word_id >= 0 and node.word_id != index:
            result.append([index, node.word_id])

        for p in node.palindrome:
            result.append([index,p])

        return result    

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()

        results = []

        for i,word in enumerate(words):
            trie.insert(i,word)
    
        for i,word in enumerate(words):
            results.extend(trie.search(i,word))

        return results  

これはかなり難しい問題です.トレイの実装と練習にもっと集中しなければなりません.