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