LeetCode 336. Palindrome Pairs

파이썬 알고리즘 인터뷰 57번(리트코드 336) Palindrome Pairs
https://leetcode.com/problems/palindrome-pairs/

나의 풀이(Time Limit Exceeded, 실패)

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        result = []
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                s = words[i] + words[j]
                if s == s[::-1]:
                    result.append([i, j])
                s = words[j] + words[i]
                if s == s[::-1]:
                    result.append([j, i])
        return result

• 당연히 처음 해볼 수 있는 접근이고 실패

다른 풀이1

# 트라이 저장할 노드
class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.word_id = -1
        self.palindrome_word_ids = []

class Trie:
    def __init__(self):
        self.root = TrieNode()

    @staticmethod
    def is_palindrome(word: str) -> bool:
        return word[::] == word[::-1]

    # 단어 삽입
    def insert(self, index, word) -> None:
        node = self.root
        for i, char in enumerate(reversed(word)):
            if self.is_palindrome(word[0:len(word) - i]):
                node.palindrome_word_ids.append(index)
            node = node.children[char]
        node.word_id = index

    def search(self, index, word) -> List[List[int]]:
        result = []
        node = self.root

        while word:
            # 판별 로직 3: 앞 단어가 더 긴 경우. 상쇄하고 남은 부분이 팰린드롬인지 확인
            if node.word_id >= 0:
                if self.is_palindrome(word):
                    result.append([index, node.word_id])
            if not word[0] in node.children:
                return result
            node = node.children[word[0]]
            word = word[1:]

        # 판별 로직 1: 앞 단어, 뒷 단어 길이 같은 경우. 정확히 서로 역순인지 확인
        if node.word_id >= 0 and node.word_id != index:
            result.append([index, node.word_id])

        # 판별 로직 2: 앞 단어가 더 짧은 경우. 상쇄하고 남은 부분이 팰린드롬인지 확인
        for palindrome_word_id in node.palindrome_word_ids:
            result.append([index, palindrome_word_id])

        return result

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

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

        results = []
        for i, word in enumerate(words):
            results.extend(trie.search(i, word))

        return results

• Trie에 단어의 역순을 삽입하고, 각 노드에서 팰린드롬 여부를 체크함.
• n을 word 개수, m을 최대 word의 길이라 할 때 내 풀이는 O(n²m), 이 풀이는 O(nm²)의 시간 복잡도이다. 일반적으로 n>m이긴 하겠지만, 이건 사실 테스트 케이스에 따라 빠른 풀이가 달라질 수 있다.

다른 풀이2

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        word_dict = {word: i for i, word in enumerate(words)}
        result = []
        
        for index, word in enumerate(words):
            n = len(word)
            for j in range(n + 1):  # 모든 가능한 분할 지점
                prefix, suffix = word[:j], word[j:]
                
                # 1. suffix가 팰린드롬이고, prefix의 역순이 단어 리스트에 존재하는 경우
                if suffix == suffix[::-1] and prefix[::-1] in word_dict:
                    pair_index = word_dict[prefix[::-1]]
                    if pair_index != index:
                        result.append([index, pair_index])
                
                # 2. prefix가 팰린드롬이고, suffix의 역순이 단어 리스트에 존재하는 경우
                # (j > 0은 중복 방지: 빈 문자열이 고려될 경우 중복 발생 가능)
                if j > 0 and prefix == prefix[::-1] and suffix[::-1] in word_dict:
                    pair_index = word_dict[suffix[::-1]]
                    if pair_index != index:
                        result.append([pair_index, index])
        
        return result

• 각 단어의 모든 분할 지점마다, 접두사 또는 접미사가 팰린드롬일 경우 반대쪽 문자열의 역순이 다른 단어에 존재하는지 확인함.

다른 풀이3

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        unique_length = set(len(word) for word in words)
        inverse_word_dict = {word[::-1]:i for i, word in enumerate(words)}

        output = []

        for i, word in enumerate(words):
            l = len(word)
            if l == 0:
                continue
            
            if word != word[::-1] and word in inverse_word_dict:
                output.append([i, inverse_word_dict[word]])

            for j in range(1, l + 1):
                if l - j in unique_length:
                    if word[:j] == word[(j - 1)::-1] and word[j:] in inverse_word_dict:
                        output.append([inverse_word_dict[word[j:]], i])
                    if word[-j:] == word[:-(j + 1):-1] and word[:-j] in inverse_word_dict:
                        output.append([i, inverse_word_dict[word[:-j]]])
        
        return output

• unique_length 를 이용해서 분할 지점 중 길이가 없는 경우는 애초에 검사하지 않아서 훨씬 빠름.

• 이 문제는 풀이를 보고 이해하는데도 한참 걸렸다. 꼭 여러번 복습하자.
• 그리고 풀이 도중 @staticmethod라는 처음 보는 표현이 나온다. 클래스의 정적 메서드인데 이외에도 @classmethod, @property등이 있고 이러한 것을 decorator(데코레이터)라고 한다. 이에 대해 아래 글에서 자세히 정리해본다.

파이썬 클래스 메서드 총정리: 인스턴스 메서드, 정적 메서드, 클래스 메서드, 그리고 특수 메서드까지