336. Palindrome Pairs

[zeikar]

Problem link

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

Problem Summary

문자열들이 주어질 때 팰린드롬이 되는 페어를 전부 구하는 문제.

Solution

단순 완전 탐색을 하면 시간 초과가 된다.

살짝 고민하면 문자열이 팰린드롬이 되도록 하는 다른 문자열을 찾는 방법을 생각해볼 수 있다.
즉, 문자열을 left, right로 나눴을 때 right가 팰린드롬이면 left의 역순을 오른쪽에 붙인 문자열이 팰린드롬이 될 것이다. 비슷하게 left가 팰린드롬이면 right의 역순을 왼쪽에 붙인 문자열이 팰린드롬이 될 것이고 이를 만족하는 문자열을 찾을 수 있다.

좀 더 파이썬하게 써보면 아래와 같다.

left + right + left[::-1]
right[::-1] + left + right

여기서 주의할 점은 빈 문자열이 있는데 이건 그냥 따로 처리해주면 된다.

Source Code

from typing import List


class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(s):
            return s == s[::-1]

        wmap = {}
        for i in range(len(words)):
            wmap[words[i]] = i

        res = []
        for i in range(len(words)):
            if words[i] == "":
                for j in range(len(words)):
                    if i != j and is_palindrome(words[j]):
                        res.append([i, j])

            for j in range(len(words[i])):
                left = words[i][:j]
                right = words[i][j:]

                # left + right + left[::-1]
                if is_palindrome(right):
                    if left[::-1] in wmap and wmap[left[::-1]] != i:
                        res.append([i, wmap[left[::-1]]])

                # right[::-1] + left + right
                if is_palindrome(left):
                    if right[::-1] in wmap and wmap[right[::-1]] != i:
                        res.append([wmap[right[::-1]], i])

        return res