[圖解 Leetcode] Longest Palindrome

Leetcode 409. 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
    }
} 

網頁瀏覽量: 0


尚未有留言,成為第一個留言的人吧!

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *