Skip to main content

336. Palindrome Pairs

문제​

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

  • 0 <= i, j < words.length,
  • i != j, and
  • words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

예제 입출력​

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
참고

You can read the full description here.

책에 있는 풀이​

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 1​

image-20230220183309526

교재 예제: 입력값이 ['d', 'cbbcd', 'dcbb', 'dcbc', 'cbbc', 'bbcd'] 인 경우

image-20230220183348402

접근법​

  1. TrieNode 클래스를 별도로 선언합니다.
  2. 단어들을 뒤집어서 트라이에 넣습니다.
  3. 팰린드롬을 찾을 때 경우의 수는 크게 3가지 입니다.
    1. 트라이의 단어와 길이가 같을 때
    2. 트라이의 단어보다 길이가 모자랄 때
    3. 트라이의 단어보다 길이가 길 때
  4. 위의 2, 3번 경우에서는 더 긴 쪽의 남은 부분이 트라이를 만족시켜야합니다.
  5. 시간복잡도를 위해 트라이 자체에 메모를 해둡니다.

구현 코드​

import collections
from typing import List


# 트라이 저장할 노드
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