[4부 비선형 자료구조] 16장 트라이

📌 56) 트라이 구현 ( 리트코드 208. Implement Trie (Prefix Tree) )

✔ 풀이

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.word = False
        self.children = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    #삽입
    def insert(self, word: str) -> None:
        node = self.root  #처음 위치
        for char in word:
            node = node.children[char]  #node를 다음 문자로 이동
        node.word = True  #단어가 완성되면 마지막 문자 노드에서 True로 표시
    
    #해당 단어가 존재하는지 여부 판별
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]   #node를 다음 문자로 이동
        return node.word
        
    #해당 문자열로 시작하는 단어가 있는지 여부 판별
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]   #node를 다음 문자로 이동
        return True

📌 57) 팰린드롬 페어 ( 리트코드 336. Palindrome Pairs )

✔ 풀이1 (팰린드롬을 브루트 포스로 계산)

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(strs):
            return strs == strs[::-1]
        
        answer = []
        
        for i, word1 in enumerate(words):
            for j, word2 in enumerate(words):
                if i == j:
                    continue
                if is_palindrome(word1 + word2):
                    answer.append([i, j])
        
        return answer

Time Limit Exceeded 시간 제한 초과 👉 더 효율적인 풀이 필요!

✔ 풀이2 (트라이 구현)

💡 판별 로직 : word[i] + word[j]가 팰린드롬이 되는 경우

word1 = word[i], word2 = word[j] 라고 가정

1️⃣ word1 == word2[::-1] & word2 == word1[::-1]일 경우, word1 + word2와 word2 + word1 는 팰린드롬이 됨.
👉word1 + word2 = word2[::-1] + word2
👉word2 + word1 = word1[::-1] + word1

2️⃣word2 == 팰린드롬 문자열 + word1[::-1] 일 경우, word1 + word2는 팰린드롬이 됨.
👉 word1 + word2 = word1 + 팰린드롬 문자열 + word1[::-1]

3️⃣word1 == word2[::-1] + 팰린드롬 문자열 일 경우, word1 + word2는 팰린드롬이 됨.
👉 word1 + word2 = word2[::-1] + 팰린드롬 문자열 + word2

💡 구현 코드👇

from collections import defaultdict
class TrieNode:
    def __init__(self):
        self.word_id = -1
        self.pelindrome_word_ids = []
        self.children = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    @staticmethod
    def is_pelindrome(word): 
        #클래스 및 객체와 연관되어 있는 것은 메서드 
        #독립적으로 존재하는 것은 함수
        #해당 메서드를 독립적으로 존재하는 함수로 만들어주기위해 데코레이터  @staticmethod로 선언
        return word[::] == word[::-1]
        
    def insert(self, idx, word):  #문자를 역순으로 삽입
        node = self.root
        for i, char in enumerate(reversed(word)):
            if self.is_pelindrome(word[0:len(word) - i]):
                node.pelindrome_word_ids.append(idx)
            node = node.children[char]
        node.word_id = idx
    
    def search(self, idx, word):
        result = []
        node = self.root
        
        #3번째 판별로직
        while word:
            #탐색 중 word_id의 값이 있을 경우
            if node.word_id >= 0:
                if self.is_pelindrome(word): #뒤의 나머지 문자열이 팰린드롬인지 확인
                    result.append([idx, node.word_id])
            #탐색 중 찾는 문자가 없을 경우
            if word[0] not in node.children:
                return result
            node = node.children[word[0]]  #노드 이동
            word = word[1:]
            
        #1번째 판별로직
        if node.word_id >= 0 and node.word_id != idx:
            result.append([idx, node.word_id])
            
        #2번째 판별로직
        for pelindrome_id in node.pelindrome_word_ids:
            result.append([idx, pelindrome_id])
            
        return result
        
        
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        
        #트라이 구현 (값 삽입)
        for idx, word in enumerate(words):
            trie.insert(idx, word)
        
        results = []
        for idx, word in enumerate(words):
            results.extend(trie.search(idx, word))
            
        return results