題目

  • 題目連結
  • 目標函式 : longestPalindrome(s)
    • Input : s: str
    • Output : int

解題概念

  • 題意 : 給定一字串 s (包含大小寫英文字母)，需要回傳可以由這些字母組合出的最長迴文長度

我的寫法

  • 想法 :
    1. 使用 Hashmap hashmap 去儲存每個字母的個數
    2. 取得 hashmap 中所有字母的奇數個數 odd_cnt
    3. 依照 odd_cnt 去回傳不同的結果 :
      • 若 odd_cnt > 1 : 先將 len(s) 減去 odd_cnt (計算出所有可兩兩配對的字母個數)，再減去 1 (一個字母置於中間)
      • 若 odd_cnt <= 1 : 代表所有字母皆可兩兩成對，因此直接回傳 len(s) 即可
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def longestPalindrome(self, s):
        
        hashmap = dict()
        odd_cnt = 0
        for i in s:
            if i in hashmap:
                hashmap[i] += 1
            else:
                hashmap[i] = 1

        for i in hashmap:
            if hashmap[i] % 2 == 1:
                odd_cnt += 1

        if odd_cnt > 1 : 
            return len(s) - odd_cnt + 1 
        else:
            return len(s)
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 18 ms (faster than 77.04%)
    • Memory Usage: 13.31 MB (more than 68.72%)

解答 or 其他優秀寫法

  • 想法 :
    1. 把 Hashmap 改成 List，只儲存兩兩成對的字母
    2. 省去 odd_cnt 的計算，可直接使用 len(t_list) 來計算
    3. 回傳的部分跟我寫法相同
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def longestPalindrome(self, s):
        
        if not s or len(s) == 0:
            return 0

        t_list = list()

        for i in s:
            if i in t_list: # 若 i 已在 t_list 中
                t_list.remove(i) # 代表 i 兩兩成對，故將 i 從 t_list 中移除
            else:
                t_list.append(i)

        if len(t_list) != 0:
            return len(s) - len(t_list) + 1 
        else:
            return len(s)
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 21 ms (faster than 59.01%)
    • Memory Usage: 13.29 MB (more than 94.28%)