Question

267. 回文排列 II

English Version

题目描述

给定一个字符串 s ，返回 _其重新排列组合后可能构成的所有回文字符串，并去除重复的组合_ 。

你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。

 

示例 1：

输入: s = "aabb"
输出: ["abba", "baab"]

示例 2：

输入: s = "abc"
输出: []

 

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

解法

方法一：回溯

回文排列需要满足至多有一个字符出现奇数次数。若不满足条件，答案提前返回。

找到出现奇数次的字符，作为中间字符（可以为空），分别向两边扩展，构造回文串。若串的长度与原串长度相等，将该串添加到答案中。

时间复杂度 $O(n \times \frac{n}{2}!)$。其中 $n$ 为字符串 $s$ 的长度。

class Solution:
  def generatePalindromes(self, s: str) -> List[str]:
    def dfs(t):
      if len(t) == len(s):
        ans.append(t)
        return
      for c, v in cnt.items():
        if v > 1:
          cnt[c] -= 2
          dfs(c + t + c)
          cnt[c] += 2

    cnt = Counter(s)
    mid = ''
    for c, v in cnt.items():
      if v & 1:
        if mid:
          return []
        mid = c
        cnt[c] -= 1
    ans = []
    dfs(mid)
    return ans

class Solution {
  private List<String> ans = new ArrayList<>();
  private int[] cnt = new int[26];
  private int n;

  public List<String> generatePalindromes(String s) {
    n = s.length();
    for (char c : s.toCharArray()) {
      ++cnt[c - 'a'];
    }
    String mid = "";
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] % 2 == 1) {
        if (!"".equals(mid)) {
          return ans;
        }
        mid = String.valueOf((char) (i + 'a'));
      }
    }
    dfs(mid);
    return ans;
  }

  private void dfs(String t) {
    if (t.length() == n) {
      ans.add(t);
      return;
    }
    for (int i = 0; i < 26; ++i) {
      if (cnt[i] > 1) {
        String c = String.valueOf((char) (i + 'a'));
        cnt[i] -= 2;
        dfs(c + t + c);
        cnt[i] += 2;
      }
    }
  }
}

class Solution {
public:
  int n;
  vector<string> ans;
  unordered_map<char, int> cnt;

  vector<string> generatePalindromes(string s) {
    n = s.size();
    for (char c : s) ++cnt[c];
    string mid = "";
    for (auto& [k, v] : cnt) {
      if (v & 1) {
        if (mid != "") {
          return ans;
        }
        mid += k;
      }
    }
    dfs(mid);
    return ans;
  }

  void dfs(string t) {
    if (t.size() == n) {
      ans.push_back(t);
      return;
    }
    for (auto& [k, v] : cnt) {
      if (v > 1) {
        v -= 2;
        dfs(k + t + k);
        v += 2;
      }
    }
  }
};

func generatePalindromes(s string) []string {
  cnt := map[byte]int{}
  for i := range s {
    cnt[s[i]]++
  }
  mid := ""
  ans := []string{}
  for k, v := range cnt {
    if v%2 == 1 {
      if mid != "" {
        return ans
      }
      mid = string(k)
    }
  }
  var dfs func(t string)
  dfs = func(t string) {
    if len(t) == len(s) {
      ans = append(ans, t)
      return
    }
    for k, v := range cnt {
      if v > 1 {
        cnt[k] -= 2
        c := string(k)
        dfs(c + t + c)
        cnt[k] += 2
      }
    }
  }
  dfs(mid)
  return ans
}