[알고리즘] Leetcode #336 팰린드롬 페어 (Python)

---

↓↓↓ 아래는 내 리트코드 & 깃허브 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

https://github.com/GodJiLee

GodJiLee - Overview

---

문제 설명

Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

 

입출력 예

Example 1:

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

Example 2:

Input: words = ["bat","tab","cat"] Output: [[0,1],[1,0]] Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""] Output: [[0,1],[1,0]]

 

Constraints

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lower-case English letters.

 

Code

# 전체 코드
import collections
# 트라이를 저장할 노드
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):
        result = []
        node = self.root
        
        while word:
            # 판별 로직 3) 탐색 중간에 word_id가 있고, 나머지 문자가 팰린드롬인 경우
            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) 끝까지 탐색했을 때 word_id가 있는 경우 
        if node.word_id >= 0 and node.word_id != index:
            result.append([index, node.word_id])
            
        # 판별 로직 2) 끝까지 탐색했을 때 palindrome word_ids가 있는 경우
        for palindrome_word_id in node.palindrome_word_ids:
            result.append([index, palindrome_word_id])
            
        return result

class Solution:
    def palindromePairs(self, words):
        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 뼈대에 팰린드롬 예제에 맞춰 약간의 변형 (T/F 대신 word_id 부여) 하고 reverse된 word를 insert하는 연산에서도 is_palindrome 함수를 활용해 팰린드롬일 때 index를 추가하도록 하였다. 여기서 슬라이싱 기능으로 구현한 is_palindrome 함수는 @staticmethod 데코레이터로 쓰여졌는데, 이는 클래스와 독립적인 함수로 선언한 것이다. 이를 종합하여 palindromePairs에서는 트라이 구조에 입력받은 word 리스트 내 문자들과 index를 insert하고, search 함수로 판별로직 1~3을 확인하여 팰린드롬 쌍이 될 수 있는 문자들의 리스트 내 위치를 return한다.

• 판별 로직

1. 애초에 단어를 반대로 뒤집어 insert하였기 때문에, 원래대로 단어를 탐색하였을 때, 맨 마지막에 word_id가 있다는 것은 역순 단어와 원래 단어가 동일하다는 의미이다.
2. palindrome word_id는 애초에 단어 자체가 팰린드롬일 때만 (is_palidrome 함수로 판별) 부여되므로, 끝까지 탐색한 하나의 단어에 palindrome word_id가 있다면 그 단어는 팰린드롬이다.
3. 중간에 word_id가 있고 나머지가 팰린드롬이라면? 'dc' + 'cbbccd' 처럼 앞뒤로 역순으로 같은 단어가 존재하고 중간에 그자체로 팰린드롬인 단어가 있는 형태이므로 이 둘을 조합하면 팰린드롬이 된다.