哈希集合：求解《409. 最长回文串》

Golang 中的 Set

• 用 map 实现 set，用 _, ok := map[key] 检查元素是否可用
• 将 value 设为空结构体 struct{}，空结构体不占用内存空间

type void struct{}
var vaule void
set := make(map[string]void) // Create Empty Set
set['key'] = vaule // Add
for key := range set { fmt.Println(key) } // Loop
delete(set, 'key') // Delete
size := len(set) // Size
_, ok := set['key']  // Check

例题

409. 最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串。 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

答案

哈希集合 · 集合

var longestPalindrome = function(s) {
  const h = new Set, n = s.length
  let r = 0
  for (let i = 0; i < n; i++) {
    if (h.has(s[i])) {
      h.delete(s[i])
      r += 2
    } else {
      h.add(s[i])
    }
  }
  return r + (h.size ? 1 : 0)
};

func longestPalindrome(s string) int {
  type void struct{}
  var value void
  set := make(map[byte]void)
  n := len(s)
  r := 0
  for i := 0; i < n; i++ {
    _, ok := set[s[i]]
    if ok {
      delete(set, s[i])
      r += 2
    } else {
      set[s[i]] = value
    }
  }
  if len(set) > 0 {
    return r + 1
  } else {
    return r
  }
}