leetcode : Palindrome Pairs

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

Palindrome Pairs - LeetCode

 

Naive하게 생각해보면 N개의 word에 대해서 나머지 N-1개의 word를 직접 갖다 붙여보면서 palindrome인지 아닌지 검사하는 방법이 있다. word길이가 K라고 할 때 O(N^2 K)라는 어마무시한 시간복잡도를 가지게 된다.

 

우린 N의 차수를 줄여줄 필요가 있다. 잘 생각해보면 무식한 방법에서는 필요없는 연산을 많이 한다. 예를 들어 abb라는 문자열이 있다고 치자. 뒤에 뭘 붙여야 palindrome을 완성할 수 있을까? a, ba, bba 등이 올 수 있을 것이다. 뒤에 뭔가를 붙여서 palindrome이 되려면 그 붙여질 단어의 맨 끝글자는 abb의 첫글자와 같아야 한다. 그니까 끝이 a가 아닌 단어들은 굳이 붙여보고 검사할 필요가 없다는 것이다. 문자열.. prefix.. suffix.. -> 떠오르는 자료구조 Trie! 

 

일단 아이디어는 간단하다. 매치가 되는 케이스는 크게 3가지다.

1. empty string과 palindrome

단어 하나가 완전히 palindrome이라면 empty string과 매치될 수 있다. 그것도 양쪽으로.

ex) "" + "aba", "aba" + ""

 

2. 한쪽은 길고 한쪽은 짧은경우

아마 가장 흔한 케이스일 것이다. 짧은 문자열이랑 긴 문자열을 붙여서 palindrome이 되는 경우

ex ) "aabb" + "aa"

 

3. 길이가 같은 두 문자열

길이가 같고 한 문자열을 뒤집었을 때 다른 문자열이 된다면 두 문자열을 붙였을때 palindrome이 된다.

ex) "aab" + "baa", "baa" + "aab"

 

이 세 가지 케이스는 하나로 일반화시킬 수 있다.

문자열을 K개의 방법으로 쪼개서 비교해보는거다.

예를 들어 "abbc"가 있다고 치면

"" "abbc"

"a" "bbc"

"ab" "bc"

"abb" "c"

"abbc" ""

 

이렇게 쪼개는 것이다. 그리고 쪼개진 문자열이 palindrome인지 검사하고(empty string은 palindrome으로 친다) 만약 맞다면 다른 문자열을 뒤집어서 반대쪽에 붙여주면 palindrome이 된다.

""와 "abbc"를 보자.

""는 palindrome이니까 "abbc"를 뒤집어서("cbba") 반대쪽(왼쪽)에 갖다붙여주면

"cbba" + "" + "abbc" = "cbbaabbc" palindrome이 된다.

그럼 우리는 "cbba"가 워드리스트에 있는지 없는지만 조사하면된다. 이 조사를 빨리하는게 핵심인데 O(K)시간 내에 할 수 있어야 한다. 여기에 dictionary나 trie를 쓰면 된다. dictionary는 검색속도가 O(1)으로 trie보다 빠를거같지만 사실은 O(K)다. K길이의 문자열을 해싱하는 알고리즘이 O(K)이기 때문..

 

한가지 주의할건 "" "abbc"나 "abbc" ""나 둘다 empty string이 있기 때문에 중복계산 안되게 주의해야된다는거. 그리고 자기 자신이 완전한 palindrome일때 (ex : "aba") "" + "aba"조합으로 쪼개서 "aba"를 사전에 검색하면 자기 자신이 나올건데 이럴때는 정답리스트에 답을 추가하면안된다. [1,1]이런식으로 같은 인덱스가 두번 나오는 식으로 추가되면 안돼! 이런 자잘한 케이스 처리때문에 if문이 살짝은 복잡해졌다.

 

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        wdict = {word[::-1] : index for index,word in enumerate(words)}
        
        answer = []
        
        for index,word in enumerate(words):
            for i in range(len(word)+1):
                prefix = word[:i]
                suffix = word[i:]

                if prefix == prefix[::-1] and suffix in wdict and wdict[suffix] != index:
                    answer.append([wdict[suffix], index])
                
                if i != len(word) and suffix == suffix[::-1] and prefix in wdict and wdict[prefix] != index:
                    answer.append([index, wdict[prefix]])
        
        return answer

 

이건 사실 다른 사람 풀이를 좀 참고한건데 같은 O(NK^2)이어도 어떤건 TLE가 뜨고 어떤건 아니다. 자잘한 python specific 최적화 방법도 좀 알아두면 좋은듯..