Question

267. Palindrome Permutation II

中文文档

Description

Given a string s, return _all the palindromic permutations (without duplicates) of it_.

You may return the answer in any order. If s has no palindromic permutation, return an empty list.

 

Example 1:

Input: s = "aabb"
Output: ["abba","baab"]

Example 2:

Input: s = "abc"
Output: []

 

Constraints:

• 1 <= s.length <= 16
• s consists of only lowercase English letters.

Solutions

Solution 1

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
}