710 - Python LeetCode

【Leetcode】python - [409] Longest Palindrome 個人解法筆記

題目出處

409. Longest Palindrome

難度

easy

個人範例程式碼

class Solution:
    def longestPalindrome(self, s: str) -> int:
        if not s: # input handling
            return 0

        ans = 0
        contains_odd = 0
        word_counter = self.counter(s) # 直接使用等同於 collections.Counter(s)，就不用另外自己寫 counter
        for key, value in word_counter.items():
            if value % 2 == 0:
                ans += value
            else:
                ans = ans + value - 1
                if contains_odd:
                    pass
                else:
                    contains_odd = 1

        return ans + contains_odd

    def counter(self, s):
        counter = {}
        for char in s:
            if char not in counter:
                counter[char] = 1
            else:
                counter[char] += 1

        return counter

算法說明

原本想要直接用 counter 把這題爆出來，後來發現 Lintcode 似乎沒有內建這種東西，我就自己重寫了一個

後來發現其實還是有 collections 可以用，但反正都寫了就這樣吧~

另外要注意的事情：

  • 當偶數的時候，直接加上去
  • 當奇數的時候，-1後加上去，並保留最多一個中心點。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

注意沒有輸入的時候的處理，input 為空白的時候 return 個 0 給他

Boundary conditions

我們這題沒辦法，「一定要把每個元素都看過」，至少 O(n)，

Reference