2131. Longest Palindrome by Concatenating Two Letter Words

문제

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/

접근

#해시테이블

중복되는 문자열을 체크해야 하므로, 파이썬의 딕셔너리(해시테이블) seen를 사용한다. 이 때 defaultdict(int)를 사용해 초기값을 0으로 한다.

words를 순회하며 각 word마다 palindrome에 해당하는 complement문자열을 만든다. 만약 이 문자열이 seen안에 존재하면 palindrome을 형성할 수 있다고 판단하고 결과값에 각 문자열의 길이의 합인 4를 더한다.

계산이 끝나고 남은 seen[complement]의 값이 0이라면 더 이상 필요 없는 값이므로 삭제한다.

여기까지 구한 것은 정 가운데의 w[0]==w[1]인 값을 뺀 palindrome의 길이이므로, seen에 값이 남아 있다면 이 정 가운데 값을 찾으러 다시 한 번 seen을 순회한다. 단 하나의 값만 찾으면 된다.

코드

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        from collections import defaultdict
        
        seen = defaultdict(int)
        result = 0

        for word in words:
            complement = word[1] + word[0] # 순서를 바꾼 문자열
            if seen[complement] > 0:  # 이 값이 seen딕셔너리 안에 존재하면
                result += 4 # 결과값 +4 (앞뒤로 2개씩 붙어서)
                seen[complement] -= 1 # 쌍이 되는 값을 차감한다.
                if seen[complement]==0: # 만약 값이 0이면
                    del seen[complement]  # 삭제
            else:
                seen[word] += 1 # seen에 존재하지 않으면 word키를 추가한다.
        
        # seen에 값이 남아있으면, 정 가운데 위치한 palindrome을 찾는다.
        for word in seen:
            if seen[word] > 0 and word[0] == word[1]:
                result += 2
                break # 한 개만 필요하므로 하나를 찾으면 break
                
        return result    

효율성

Runtime: 3631 ms, faster than 23.05% of Python3 online submissions for Longest Palindrome by Concatenating Two Letter Words.
Memory Usage: 38.3 MB, less than 54.38% of Python3 online submissions for Longest Palindrome by Concatenating Two Letter Wor