Leetcode - 336. Palindrome Pairs

문제 링크 : leetcode 336 문제

문제: 단어리스트에서 words[i] + word[j]가 펠린드롬이 되는 모든 인덱스 조합(i,j)를 구하라.

풀이 1.(브루트 포스)
두 단어를 모두 합쳐보고 그 단어가 펠린드롬인지 확인하였다.

def palindromePairs(self, words):
        
        def check(word1,word2):
            word = word1 + word2

            if word == word[::-1]:
                return True
            else:
                return False
        
        result = []
    
        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue
                else:
                    if check(words[i],words[j]):
                       result.append([i,j])
        
        return result               

하지만 결과는 Runtime Error였다. 아무래도 O(n^2)의 시간복잡도이다 보니 무리가 있었다.

그렇다면 어떤 풀이가 적합할까??
내가 선택한 것은 트라이(Trie)이다.

트라이를 사용하면 아무래도 시간복잡도가 찾고자하는 문자열이 길이이기 때문에 앞서 풀어본 브루트포스의 시간복잡도 문제를 해결할 수 있을 것이다.

시간복잡도가 O(n)인 상태에서 풀기 위해서는 모든 입력값을 트라이로 만들어두고 딱 한 번씩만 탐색하는 문제로 변형할 것이다. 펠린드롬을 판별하려고 하니 입력받은 문자를 뒤집어서 트라이에 집어넣을 것이다.

입력값 예제를 ['d','cbbcd','dcbb', 'dcdc',cbbc','bbcd'] 정도로 좀 복잡한 값을 입력값으로 해서 뒤집어서 밑의 그림과 같이 표현하였다.

뒤집어놓은 입력값을 기존의 트라이 구현(삽입)을 통해 구현한 모습을 그림으로 나타내어 보았다.
w는 해당 단어가 있다는 것을 뜻하고 옆에 있는 변수는 주소값을 나타낸 것이다.

따라서 이러한 트라이를 통해서 입력값을 집어넣어서 펠린드롬인지 아닌지 확인하려고 하는 것이다. 그렇다면 펠린드롬을 어떻게 구분할 수 있을까??

1. 탐색 중간에 w가 있을 때

 while word:
            # node.word > -1이 있다는 뜻은 펠린드롬 될 수 있는 항목이 다른 입력값에 존재한다는 뜻
            if node.word_id > -1:
                # 그 나머지 입력값들이 펠린드롬이라면 그 수는 펠린드롬
                if self.isPalindrome(word):
                    #결과값에 인덱스와 해당 노드이 인덱스를 넣어준다.
                    result.append([index,node.word_id])
            
            if not word[0] in node.children:
                return result
            
            node = node.children[word[0]]
            word = word[1:]
	

뒤집지 않은 단어를 입력받아 만약 해당 단어에 w표시가 있다면 뒤의 나머지 문자의 펠린드롬 여부를 판단하여 펠린드롬 여부를 판단한다.

입력값 : ['d', 'cbbcd', 'dcbb', 'dcbc', 'cbbc', 'bbcd'] 중 'dcbbc'를 예로 들어보자.

1) 만약 'dcbc'에서 첫번째 값인 d를 꺼낸다.
2) d 노드의 w = 0으로 표시되어 있어 나머지 문자의 펠린드롬 여부를 검사한다. => 'cbc'이므로 펠린드롬이다. 따라서 dcbc+d 즉, 펠린드롬이 된다.

2. 입력값 = 뒤집은 트라이

#순서대로 끝까지 탐색한 후 
#만약 node.word_id가 0보다 같거나 크고 index가 서로 다르다면(ex) "abcd", "dcba"와 같은)
if node.word_id >= 0 and node.word_id != index:
	result.append([index, node.word_id])

앞서 word[1:]구문으로 입력값을 하나씩 탐색하면서 펠린드롬 값을 찾았다. 하지만 그 과정에서 'abcd',dcba'와 같은 펠린드롬이 없어도 펠린드롬이 되는 입력값 = 뒤집은 트라이은 추출하지 못하였다.

앞서 입력값 : ['d', 'cbbcd', 'dcbb', 'dcbc', 'cbbc', 'bbcd'] 중 'bbcd'를 예를 들어보자.

앞서 삽입함수를 통해 'dcbb'가 뒤집어져 그림의 빨간색의 트리를 완성시켰다. 따라서 탐색함수에서 'bbcd'를 입력하면 트리 끝부분까지 갈 것이고(w > 0) 이렇게 된다면 우리는 펠린드롬이라 할 것이다.

3. 끝까지 탐색했을 때 p가 있을 경우

p? 많이 의아할 것이다. 이 p는 앞서 삽입함수 때 넣은 것으로 설명하지 않았다.

그렇다면 p는 무엇일까?? 앞서 삽입함수에서 입력받은 단어를 뒤집어서 넣었다. 그때 한 단어씩 트리에 넣는다고 할때 나머지 부분이 펠린드롬이라면 그것을 메모이제이션을 통해 해당 노드에 P값을 저장하였다. 그림으로 나타내면 다음과 같다.

그렇다면 이 메모이제이션을 통해 어떤 펠린드롬을 찾을 수 있는지 살펴보자.

앞서 입력값 : ['d', 'cbbcd', 'dcbb', 'dcbc', 'cbbc', 'bbcd'] 중 'dcbb'를 예를 들어보자.

입력값 dcbb의 마지막 노드가 p = 1이다. 그렇다는 말은 dcbb + c(메모이제이션) + bbcd를 통해 펠린드롬이 된다는 뜻이다.

그렇다면 root에 저장된 p = 0, p = 4는 무엇일까??
눈치채신 분들도 있으시겠지만 그것은 바로 원래의 입력값이 펠린드롬인 것이다.

코드는 다음과 같다.

# 2 : 펠린드롬값 + 입력값 찾기
# 끝까지 탐색했을 때 그 노드에 펠린드롬 표시가 있다면 그 단어는 펠린드롬이다. 
for p in node.palindrome:
    result.append([index,p])

전체코드
w를 word_id
p를 palidrome리스트로 표현하였습니다.

class Node:
    def __init__(self,key):
        self.key = key
        self.palindrome = []
        self.word_id = -1
        self.children = {}

class Trie(object):
    def __init__(self):
        self.root = Node(None)

    @staticmethod
    def isPalindrome(word):
        return word[::] == word[::-1]

    def insert(self, index, word):
        node = self.root

        for i, ch in enumerate(reversed(word)):
            if self.isPalindrome(word[:len(word)-i]):
                node.palindrome.append(index)
            
            if ch not in node.children:
                node.children[ch] = Node(ch)

            node = node.children[ch]    

        node.word_id = index       

    def search(self, index, word):
        node = self.root

        result = []

        while word:
            if node.word_id > -1:
                if self.isPalindrome(word):
                    result.append([index,node.word_id])
            if not word[0] in node.children:
                return result
            
            node = node.children[word[0]]
            word = word[1:]

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

        for p in node.palindrome:
            result.append([index,p])

        return result    

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

        results = []

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

        return results  

상당히 어려운 문제였다. 트라이 구현 및 연습에 더욱 몰두해야겠다.