[leetcode] 336. Palindrome Pairs (팰린드롬 페어)

문제 설명

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.

---

풀이

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):
            return word[::] == word[::-1]
        
        #단어 삽입
        def insert(self,index,word):
            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.val = char
            node.word_id = index
        
        def search(self,index,word):
            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(object):
    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
        

결과

---

문제 풀이

브루트 포스 풀이로 진행하면 각각의 모든 조합을 구성하고 이 구성이 팰린드롬인지 여부를 판별하면 O(n^2) 시간 복잡도로 풀이가 가능하다. 

def palindromePairs(self, words):
	def is_palindrome(word):
		return word == word[::-1]
	output = []
	for i,word in enumerate(words):
		for j, word2 in enumerate(words):
    		if i == j:
        		continue
        	if is_palindrome(word1+word2):
        		output.append([i,j])
	return output

구현이 간단하고 실행도 잘 된다. 하지만 타임아웃이 발생하여 테스트 케이스 통과가 안된다.

 

O(n^2)를 O(n)으로 풀이할 방법은 트라이(Trie)로 풀이하는 것이다.

 

모든 입력값을 트라이로 만들어두고 딱 한 번씩만 탐색하는 문제로 변형한다. 팰린드롬을 판별해야 하기 때문에 뒤집어서 트라이로 구성하면 될 것이다.

 

판별 로직 -1

단어를 뒤집어서 구축한 트라이이기 때문에 입력밧은 순서래도 탐색하다가 , 끝나는 지점의 word_id 값이 -1이 아니라면 현재 인덱스 index와 해당 word_id는 팰린드롬으로 판단할 수 있다.

판별 로직 -2

트라이 삽입 중에 남아 있는 단어가 팰린드롬이라면 미리 팰린드롬 여부를 세팅해 두는 방법이다. 

즉 입력값 ['d', 'dcbbc', 'bbcd', 'cdcd', 'cbbc', dcdd']에서 cddc는 단어 자체가 팰린드롬이므로 루트에 바로 입격 값의 인덱스인 p = 4를 세팅하고 word [0:len(word]-i] 형태로 단어에서 문자 수를 계속 줄여 나가며 팰린드롬 여부를 체크한다.

문자가 하나만 남게 될 때는 항상 팰린드롬이므로 마찬가지로 p = 4를 마지막에 세팅한다. 

판별 로직 -3

입력값을 문자 단위로 확인해 나가다가 해당 노드의 word_id가 -1이 아닐 때, 나머지 문자가 팰린드롬이라면 팰린드롬으로 판별하는 경우다. dcdc+d가 이에 해당하는데 입력값 dcbc는 먼저 d부터 탐색하다가 d의 word_id가 -1이 아니기 때문에 나머지 문자 cbc에 대한 팰린드롬 여부를 검사한다.

 

3가지 판별 로직을 다시 정리하자면,

 

1. 끝까지 탐색했을 때 word_id가 있는 경우 -> 판별 로직 -1

2. 끝까지 탐색했을 때 palindrome_word_ids가 있는 경우 -> 판별 로직 -2

3. 탐색 중간에 word_id가 있고 나머지 문자가 팰린드롬인 경우 -> 판별 로직 -3

 

이렇게 3가지 경우를 팰린드롬으로 판별할 수 있으며, 입력값을 각각 한 번씩만 대입하면 되기 때문에 O(n)으로 풀이할 수 있다.