LeetCode 267. 回文排列 II

Categories:

题目描述
思路分析
1. 解法一：回溯 + 哈希表（推荐）
相似题目

题目描述

✅ 267. 回文排列 II

思路分析

解法一：回溯 + 哈希表（推荐）

核心思路：

回文排列的充要条件：最多有一个字符出现奇数次（作为中间字符）

统计各字符频次，若奇数次字符超过 1 个，则无解，返回空列表

将每个字符取一半数量加入候选列表，对候选列表进行全排列回溯

每个排列结果拼接成完整回文串：排列 + 奇数字符（若有）+ 排列的逆序

用 visited 数组剪枝去重：同一层中跳过相同字符，避免重复排列

复杂度分析：

时间复杂度：O(n/2 * (n/2)!)，n 为字符串长度，全排列数量

空间复杂度：O(n)，递归栈与路径存储

class Solution {
  private List<String> result = new ArrayList<>();
  private char[] path;
  private boolean[] visited;

  public List<String> generatePalindromes(String s) {
    int[] count = new int[128];

    for (char c : s.toCharArray()) {
      count[c]++;
    }

    // 统计奇数次字符
    String oddChar = "";
    List<Character> half = new ArrayList<>();

    for (int i = 0; i < 128; i++) {
      if (count[i] % 2 == 1) {
        oddChar += (char) i;
      }
      // 取一半数量加入候选
      for (int j = 0; j < count[i] / 2; j++) {
        half.add((char) i);
      }
    }

    // 奇数次字符超过 1 个，无法构成回文
    if (oddChar.length() > 1) {
      return result;
    }

    char[] chars = new char[half.size()];
    for (int i = 0; i < half.size(); i++) {
      chars[i] = half.get(i);
    }

    path = new char[chars.length];
    visited = new boolean[chars.length];

    // 回溯生成全排列
    backtrack(chars, 0, oddChar);

    return result;
  }

  private void backtrack(char[] chars, int idx, String oddChar) {
    if (idx == chars.length) {
      // 构建完整回文串
      String half = new String(path);
      StringBuilder sb = new StringBuilder(half);
      sb.append(oddChar);
      sb.append(new StringBuilder(half).reverse());
      result.add(sb.toString());
      return;
    }

    for (int i = 0; i < chars.length; i++) {
      if (visited[i]) {
        continue;
      }
      // 同层剪枝：跳过重复字符
      if (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1]) {
        continue;
      }

      visited[i] = true;
      path[idx] = chars[i];

      backtrack(chars, idx + 1, oddChar);

      visited[i] = false;
    }
  }
}

func generatePalindromes(s string) []string {
    count := [128]int{}
    for _, c := range s {
        count[c]++
    }

    // 统计奇数次字符，收集一半数量字符
    oddChar := ""
    half := []byte{}

    for i := 0; i < 128; i++ {
        if count[i]%2 == 1 {
            oddChar += string(rune(i))
        }
        for j := 0; j < count[i]/2; j++ {
            half = append(half, byte(i))
        }
    }

    // 奇数次字符超过 1 个，无解
    if len(oddChar) > 1 {
        return []string{}
    }

    result := []string{}
    path := make([]byte, len(half))
    visited := make([]bool, len(half))

    var backtrack func(idx int)
    backtrack = func(idx int) {
        if idx == len(half) {
            // 构建完整回文串
            left := string(path)
            rev := reverseStr(left)
            result = append(result, left+oddChar+rev)
            return
        }

        for i := 0; i < len(half); i++ {
            if visited[i] {
                continue
            }
            // 同层剪枝去重
            if i > 0 && half[i] == half[i-1] && !visited[i-1] {
                continue
            }

            visited[i] = true
            path[idx] = half[i]

            backtrack(idx + 1)

            visited[i] = false
        }
    }

    backtrack(0)

    return result
}

func reverseStr(s string) string {
    b := []byte(s)
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
    return string(b)
}

相似题目

题目	难度	考察点
46. 全排列	中等	回溯
47. 全排列 II	中等	回溯、剪枝去重
266. 回文排列	简单	哈希表
5. 最长回文子串	中等	动态规划、双指针
131. 分割回文串	中等	回溯、动态规划
336. 回文对	困难	哈希表、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/28100444