[圖解 Leetcode] Longest Palindrome

題目

在字串 s 中找到最長的回文 (palindrome) 字串的長度，即中間對稱向兩邊相同字元，如 “abcdddee” 可以組合出最長回文字串 “deaed” ，答案就是 5

思路

此題相關考點為： Hash table 的使用

先用 Dictionary 統計出每個字母的次數

可以用

 for i in s{
      if let _ = map[i] {
          map[i]! += 1
      } else {
          map[i] = 1
     }
 }

如何用 reduce 寫可以是

let map: [Character: Int] = t.reduce(into: [:], { $0[$1, default: 0] += 1 })

統計好字母後，就是核心判斷關鍵，找到有幾個 pair，例如 aa 算 1 個 pair 就可以加 1*2 = 2，bbcccc 就是 3 個 pair 最長回文字串可以包含 3*2 = 6，

要注意判斷 center 是否需要計算進去：

像是 s = “aab”，雖然只有 1 個 pair 但是，可以 center 中間插入 b，如 “aba” 也是成立回文，

程式碼

class Solution {
    func longestPalindrome(_ s: String) -> Int {
        var map:[Character:Int] = [:]
        for i in s{
            if let _ = map[i] {
                map[i]! += 1
            }else{
                map[i] = 1
            }
        }
        var result = 0
        for i in map.values{
            result += (i / 2) // find how many pairs in string
        }
        result *= 2 // 1 pair can make 2 char
        
        if result < s.count {
            result += 1
        }
        return result
    }
}