[Leetcode] 2131. Longest Palindrome by Concatenating Two Letter Words

문제

 

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

Longest Palindrome by Concatenating Two Letter Words - LeetCode

ou 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.

 

Example 1:

Input	Output
words = ["lc","cl","gg"]	6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6. Note that "clgglc" is another longest palindrome that can be created.

 

Example 2:

Input	Output
words = ["ab","ty","yt","lc","cl","ab"]	8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8. Note that "lcyttycl" is another longest palindrome that can be created.

 

Example 3:

Input	Output
words = ["cc","ll","xx"]	2
Explanation: One longest palindrome is "cc", of length 2. Note that "ll" is another longest palindrome that can be created, and so is "xx".

 

 

문제풀이 코드

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        counter = Counter(words)
        result = mid = 0
        string = ""
        for word in counter.keys():
            # "aa", "bb" 같은 문자열
            if word[0] == word[1]:
                # "aa"의 갯수가 짝수면 갯수, 홀수면 -1 을 더해준다
                result += counter[word] if counter[word] % 2 == 0 else counter[word] - 1
                # 모든 앞뒤가 같은 단어들 중 홀수가 하나라도있으면 mid = 1
                mid |= counter[word] % 2
            # "cl", "lc" 같은 단어 일 때 
            elif word[::-1] in counter:
                # 앞뒤로 이어붙일 수 있는 단어는 둘개의 단어를 카운트 했을 때 더 갯수가 더 작은 쪽으로 더해준다
                # Ex) ["lc", "lc", "lc", "cl", "cl"] 일 때,
                # "lclcclcl"은 되지만 "lclclcclcl"은 성립하지 않는다.
                result += min(counter[word], counter[word[::-1]])
        # 모든 단어는 2글자로 되어있으니 * 2를 해준다
        return (result+mid)*2

1. 모든 단어들을 Counter함수를 통해 갯수를 샌다.

2. 단어는 "aa" 앞뒤가 같은단어 또는 "lc" 앞뒤가 다른 단어가 올 수 있다.

3. 앞뒤가 같은 단어일 때는 짝수로 나누어지면 해당 단어의 갯수를 result에 더해주고 홀수일때는 -1을 해서 짝수만큼 더해준다

4. 같은단어가 홀수개 있을 때 mid = 1

5. 앞뒤가 다른 단어일 때는 현재 단어의 갯수와 뒤집었을 때 단어의 갯수 중 더 작은 값을 result에 더해준다

6. 모든 단어는 2글자이기 때문에 (result + mid) * 2를 반환한다