1주차 보너스 - Palindrome 순열

6125 단어 pythonleetcode
이에 대한 코드가 있습니다in this GitHub Repo.

문제



Leetcode Link

Given a string, determine if a permutation of the string could form a palindrome.



예 1:

Input: "code"
Output: false


예 2:

Input: "aab"
Output: true


예 3:

Input: "carerac"
Output: true


내 테스트




import pytest
from .Week1Bonus import Solution

s = Solution()


@pytest.mark.parametrize("test_input", ["code", "abc"])
def test_cannot_permute(test_input):
    assert not s.canPermutePalindrome(test_input)


@pytest.mark.parametrize("test_input", ["aab", "carerac", "a", "aa"])
def test_can_permute(test_input):
    assert s.canPermutePalindrome(test_input)


내 솔루션




class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        if len(s) == 1:
            return True
        char_counts = {}
        for c in s:
            if c in char_counts:
                char_counts[c] = char_counts[c] + 1
            else:
                char_counts[c] = 1
        values = char_counts.values()
        num_odd = 0

        for n in values:
            if n == 1 or n % 2 != 0:
                num_odd += 1

        return num_odd < 2


분석







내 해설



좋아, 나는 이것으로 꽤 게을렀지만 너무 끔찍하지는 않았습니다.

문자열을 살펴보고 얼마나 많은 문자가 홀수 번 나타나는지 파악하면 홀수 번 나타나는 문자가 두 개 이상인지 확인하는 것이 합리적인 해결책이라고 생각했습니다. 그렇게 하면 문자열의 어떤 순열도 회문이 될 수 없습니다.

아직 더 나은 솔루션에 대해 많이 생각하지 않았으므로 팁이 있으면 알려주십시오. :)

좋은 웹페이지 즐겨찾기