[리트코드] 336 팰린드롬 페어

https://leetcode.com/problems/palindrome-pairs/

Palindrome Pairs - LeetCode

단어 리스트의 단어 조합 중 팰린드롬이 되는 모든 인덱스의 조합을 구하는 문제이다.

 

단순히 가능한 모든 조합을 구하고 팰린드롬인지 확인할 경우 해결은 가능하겠지만 시간이 오래걸린다.

따라서 문자열의 효율적인 탐색 자료구조인 트라이(Trie)를 사용해야한다.

 

데이터를 어떻게 저장해야할까?

일반적인 문자열 탐색의 경우 트라이에 문자열을 순서대로 저장할 것이다. 하지만 이 문제에서는 팰린드롬을 판별해야 하기 때문에 문자열을 역순으로 저장한다.

 

문자열을 트라이에 역순으로 저장하고, 다른 문자열을 트라이에서 탐색할 경우 팰린드롬을 쉽게 판별할 수 있기 때문에 역순으로 저장한다.

 

그리고 문자열을 구분하기 위해서 끝에 해당 문자열의 인덱스를 저장한다. 이를 word_id(w)라고 표현한다.

 

팰린드롬 판별

['d', 'cbbcd', 'dcbb', 'dcbc', 'cbbc', 'bbcd']를 예로 설명한다. 주어진 문자열 배열을 먼저 트라이에 저장한다.

 

첫 번째 판별 로직은 입력 값을 순서대로 탐색하다가 마지막 노드의 word_id 값을 확인하는 것이다.

트라이를 단어를 뒤집어 구현했기 때문에 입력 단어를 순서대로 탐색하고, 끝나는 지점의 word_id가 0 이상인 경우 현재 index와 해당 word_id의 쌍은 팰린드롬으로 판단할 수 있다. 'bbcd'를 트라이에서 검색하면 마지막 노드 'd'의 word_id 값이 2 이므로, (5, 2)는 팰린드롬이다.

if node.word_id >= 0 and node.word_id != index:
	result.append([index, node.word_id])

 

두 번째 판별 로직은 트라이 삽입 중에 남아 있는 단어가 팰린드롬이라면 미리 팰린드롬 여부를 세팅해 두는 방법이다. 역순으로 구현된 트라이에 단어를 검색하고 그 결과 단어가 존재하면 적어도 해당 단어 길이 만큼은 팰린드롬이 보장된다. 즉, 'abc'와 '???cba'를 조합하면 'abc???cba'가 되는데 '???'가 팰린드롬이면 전체가 팰린드롬인 것이다.

 

주어진 단어 배열 중 'cbbc'는 단어 자체가 팰린드롬이기 때문에 root에 4를 저장하고, 'bbcd'는 'bb'와 'b'가 팰린드롬이기 때문에 'c' 노드에 5, 'b' 노드에 5를 저장한다. 해당 노드 앞부분까지는 팰린드롬이라는 것을 나타내는 것이다. 아래 그림에서는 p(palindrome_word_ids)로 나타내었고, p에는 여러 값이 들어갈 수 있다.

for palindrome_id in node.palindrome_word_ids:
    result.append([index, palindrome_id])

 

세 번째 판별 로직은 입력 단어를 문자 단위로 확인해 나가다가 해당 노드의 word_id가 -1이 아닐 때, 나머지 문자가 팰린드롬이라면 팰린드롬으로 판별하는 경우이다. dcbc + d가 이에 해당한다.

입력 값 dcbc의 d를 먼저 탐색 하다 d 노드의 word_id가 -1이 아닌 것을 확인한다. 그리고 cdc가 팰린드롬인지 판별한다. 팰린드롬임을 확인이 되면 dcbc + d가 팰린드롬으로 판별한다.

 

while word:
    if node.word_id >= 0:
        if self.is_palindrome(word):
            result.append([index, node.word_id])
    node = node.children[word[0]]
    word = word[1:]

 

최종적으로 정리하면 다음과 같다.

1. 끝까지 탐색했을 때 word_id가 있는 경우

2. 끝까지 탐색했을 때 palindrome_word_ids가 있는 경우

3. 탐색 중간에 word_id가 있고 나머지 문자가 팰린드롬인 경우

 

Python