全排列、回溯：3 种数据结构判断能否生成回文求解《266. 回文排列》《面试题 01.04. 回文排列》递归回溯求解《267. 回文排列 II》

复习带有重复字符的全排列，3 种数据结构判断能否生成回文求解《266. 回文排列》《面试题 01.04. 回文排列》，递归回溯求解《267. 回文排列 II》

模板

带有重复字符的全排列

• 先将重复字符放到到一起
  • 全排列时，记录访问过的索引
  • 重复字符，总按照 未放问、未访问、未访问 => 访问过、未访问、未访问 => 访问过、访问过、未访问 => 访问过、访问过、访问过 顺序访问

const r = [], ar = [], n = s.length, visited = new Uint8Array(n)
const d = () => {
  if (ar.length === n) return r.push(ar.slice())<br>
  for (let i = 0; i < s.length; i++) {<br>
     if (visited[i] === 1 || i > 0 && s[i - 1] === s[i] && visited[i - 1] === 0) cotinue
     ar.push(s[i])
     d()
     ar.pop()
  }
}

判断能否生成回文

集合

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

数组 · 同构数组

var canPermutePalindrome = function(s) {
  const n = s.length, h = new Uint32Array(128)
  let odd = 0
  for (let i = 0; i < n; i++) {
    ++h[s.charCodeAt(i)] % 2 === 0 ? odd-- : odd++
  }
  return odd <= 1
};

位图 · 位比特图

var canPermutePalindrome = function(s) {
  const n = s.length, bit = new Bit
  for (let i = 0; i < n; i++) {
    bit.add(s.charCodeAt(i))
  }
  return bit.countOne() <= 1n
};
class Bit {
  constructor() {
    this.bit = 0n
  }
  add(i) {
    this.bit ^= 1n << BigInt(i)
  }
  countOne() {
    let r = 0n, n = this.bit
    while (n) {
      n &= n - 1n
      r++
    }
    return r
  }
}

Golang · Reverse 翻转数组

func reverse(ar []string) []string {
  for l, r := 0, len(ar) - 1; l < r; l, r = l + 1, r - 1 {
    ar[l], ar[r] = ar[r], ar[l]
  }
  return ar
}

Golang · 拷贝数组

• 赋值、函数传参、函数返回值都是浅拷贝

arCopy := append([]string(nil), ar)

例题

266. 回文排列

面试题 01.04. 回文排列

给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。

答案

集合

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

func canPermutePalindrome(s string) bool {
  type void struct{}
  var value void
  set := make(map[byte]void)
  for i := range s {
    _, ok := set[s[i]]
    if ok {
      delete(set, s[i])
    } else {
      set[s[i]] = value
    }
  }
  return len(set) <= 1
}

数组 · 同构数组

var canPermutePalindrome = function(s) {
  const n = s.length, h = new Uint32Array(128)
  let odd = 0
  for (let i = 0; i < n; i++) {
    ++h[s.charCodeAt(i)] % 2 === 0 ? odd-- : odd++
  }
  return odd <= 1
};

func canPermutePalindrome(s string) bool {
  h := make([]int, 128)
  odd := 0
  for _, v := range s {
    h[v]++
    if h[v] % 2 == 0 {
      odd--
    } else {
      odd++
    }
  }
  return odd <= 1
}

位图 · 位比特图

var canPermutePalindrome = function(s) {
  const n = s.length, bit = new Bit
  for (let i = 0; i < n; i++) {
    bit.add(s.charCodeAt(i))
  }
  return bit.countOne() <= 1n
};
class Bit {
  constructor() {
    this.bit = 0n
  }
  add(i) {
    this.bit ^= 1n << BigInt(i)
  }
  countOne() {
    let r = 0n, n = this.bit
    while (n) {
      n &= n - 1n
      r++
    }
    return r
  }
}

267. 回文排列 II

给定一个字符串 s ，返回 其重新排列组合后可能构成的所有回文字符串，并去除重复的组合 。 你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。

答案

递归回溯

注意 aaa 都是奇数的情况

var generatePalindromes = function(s) {
  [b, h] = canPermutePalindrome(s)
  if (b === false) return []
  const evens = []
  let odd = ''
  for (let i = 0; i < 128; i++) {
    if (h[i] === 0) continue
    evens.push(...String.fromCharCode(i).repeat(h[i] / 2))
    if (h[i] % 2 === 1) odd = String.fromCharCode(i) // 只剩一个奇数
  }
  const r = [], ar = [], n = evens.length, visited = new Uint8Array(n)
  const d = () => {
    if (ar.length === n) {
      const arCopy = ar.slice()
      return r.push([...arCopy, odd, ...arCopy.reverse()].join(''))
    }
    for (let i = 0; i < n; i++) {
      if (visited[i] === 1 || i > 0 && evens[i - 1] === evens[i] && visited[i - 1] === 0) continue
      ar.push(evens[i])
      visited[i] = 1
      d()
      visited[i] = 0
      ar.pop()
    }
  }
  d()
  return r
};
const canPermutePalindrome = s => {
  const n = s.length, h = new Uint8Array(128)
  let odd = 0
  for (let i = 0; i < n; i++) {
    ++h[s.charCodeAt(i)] % 2 === 0 ? odd-- : odd++
  }
  return [odd <= 1, h]
}

import "strings"
func generatePalindromes(s string) []string {
  h, odd := make([]int, 128), 0
  for i := range s {
    h[s[i]]++
    if h[s[i]] % 2 == 0 {
      odd--
    } else {
      odd++
    }
  }
  if odd > 1 {
    return []string(nil)
  }
  var evens []string
  oddChar := ""
  for i := 0; i < 128; i++ {
    if h[i] == 0 {
      continue
    }
    half := h[i] / 2
    for j := 0; j < half; j++ {
      evens = append(evens, string(rune(i)))
    }
    if h[i] % 2 == 1 {
      oddChar = string(rune(i))
    }
  }
  var r []string
  var ar []string
  var d func()
  n := len(evens)
  visited := make([]int, n)
  d = func() {
    if len(ar) == n {
      arCopy := append([]string(nil), ar...)
      r = append(r, strings.Join(arCopy, "") + oddChar + strings.Join(reverse(arCopy), ""))
      return
    }
    for i := 0; i < n; i++ {
      if visited[i] == 1 || i > 0 && evens[i - 1] == evens[i] && visited[i - 1] == 0 {
        continue
      }
      ar = append(ar, evens[i])
      visited[i] = 1
      d()
      visited[i] = 0
      ar = ar[:len(ar) - 1]
    }
  }
  d()
  return r
}
func reverse(ar []string) []string {
  for l, r := 0, len(ar) - 1; l < r; l, r = l + 1, r - 1 {
    ar[l], ar[r] = ar[r], ar[l]
  }
  return ar
}