iT邦幫忙

2024 iThome 鐵人賽

0
佛心分享-刷題不只是刷題

刷經典 LeetCode 題目系列 第 46

經典LeetCode 409. Longest Palindrome

  • 分享至 

  • xImage
  •  

題目:
給定一個只包含大小寫字母的字串,找出可以由這些字母組成的最長回文的長度。回文指的是正著讀和倒著讀都一樣的字串。

範例:

輸入: s = "abccccdd"
輸出: 7
解釋: 我們可以構造的最長回文是 "dccaccd",其長度為 7。

解題思路

題目是要判斷能夠建立最長回文,所以跟判斷是否是回文的解題思路就不太一樣了,

由於回文就是要成對的字母出現,也就是偶數的成對字母,頂多在加上一個中間奇數的字母,

所以我們就可以這樣去判斷,

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> map;
        for (auto c : s) {
            map[c]++;
        }

        int res = 0;
        bool hasOdd = false; // 紀錄是否有出現奇數次的字母
        for (auto m : map) {
            res += m.second / 2;
            
            if (m.second % 2 == 1) {
                hasOdd = true;
            }
        }

        return res * 2 + (hasOdd ? 1 : 0);
    }
};

參考:
#409. Longest Palindrome


上一篇
經典LeetCode 278. First Bad Version
下一篇
經典LeetCode 543. Diameter of Binary Tree
系列文
刷經典 LeetCode 題目69
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言