Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/267.html
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.
Algorithm
One thing to note is that if you use an array to save the result directly, and if there are repeated characters in t, there may be duplicates, such as t = “baa”, then the final result will have duplicates
- When start=0 and i=1, aba is obtained after the exchange,
- Later when start=1 and i=2, aab can be obtained after the exchange.
- But after returning to the first layer after baa, when start=0, i=2, aab is obtained after the exchange, and repetition occurs.
In fact, the easiest way to de-duplicate is to define the result res as a HashSet, and use its de-duplication feature to ensure that there is no duplicate.
Code
-
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class Palindrome_Permutation_II { public static void main(String[] args) { Palindrome_Permutation_II out = new Palindrome_Permutation_II(); Solution s = out.new Solution(); System.out.println(s.generatePalindromes("aabb")); System.out.println(s.generatePalindromes("aaaa")); System.out.println(s.generatePalindromes("aaaaa")); } public class Solution_lesscode { public List<String> generatePalindromes(String s) { int[] cha = new int [256]; for (int i = 0; i < s.length(); i ++) { cha[s.charAt(i)] += 1; } List<String> result = new LinkedList<String>(); boolean odd = false; int oddIndex = 0; for (int i = 0; i < 256; i ++) { if (cha[i] % 2 == 1) { if (odd == true) { return result; } oddIndex = i; odd = true; } } String base = ""; if (odd == true) { base = (char)oddIndex + ""; cha[oddIndex] -= 1; } process(base, cha, s.length(), result); return result; } private void process(String base, int[] cha, int n, List<String> result) { if (base.length() == n) { result.add(base); return; } for (int i = 0; i < cha.length; i ++) { if (cha[i] > 0) { cha[i] -= 2; process((char)i + base + (char)i, cha, n, result); cha[i] += 2; } } } } class Solution { public List<String> generatePalindromes(String s) { List<String> result = new ArrayList<>(); int odd = 0; // char => its count Map<Character, Integer> map = new HashMap<>(); // step 1. build character count map and count odds for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); map.put(c, 1 + map.getOrDefault(c, 0)); odd += map.get(c) % 2 != 0 ? 1 : -1; } // cannot form any palindromic string if (odd > 1) { return result; } // step 2. add half count of each character to list String mid = ""; List<Character> charList = new ArrayList<>(); for (Map.Entry<Character, Integer> entry : map.entrySet()) { char key = entry.getKey(); int val = entry.getValue(); if (val % 2 != 0) { // odd count char mid += key; } for (int i = 0; i < val / 2; i++) { charList.add(key); } } // step 3. generate all the permutations getPerm(charList, mid, new boolean[charList.size()], new StringBuilder(), result); return result; } // generate all unique permutation from list, sb: cur_res void getPerm(List<Character> list, String midChar, boolean[] used, StringBuilder sb, List<String> result) { if (sb.length() == list.size()) { // form the palindromic string result.add(sb.toString() + midChar + sb.reverse().toString()); sb.reverse(); // restore return; } for (int i = 0; i < list.size(); i++) { // avoid duplication if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) { // i-1 must already checked, so skip used[i - 1]==false continue; } if (!used[i]) { used[i] = true; sb.append(list.get(i)); // recursion getPerm(list, midChar, used, sb, result); // backtracking used[i] = false; sb.deleteCharAt(sb.length() - 1); } } } } } ############ 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; } } } };
-
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 ############ import collections class Solution(object): def generatePalindromes(self, s): """ :type s: str :rtype: List[str] """ def helper(s, path, ans, visited): if len(path) == len(s): ans.append("".join(path)) return for i in range(len(s)): if i > 0 and s[i] == s[i - 1] and i - 1 not in visited or i in visited: continue visited |= {i} path.append(s[i]) helper(s, path, ans, visited) path.pop() visited -= {i} ans = [] res = [] ss = "" mid = "" counter = collections.Counter(s) oddChars = filter(lambda x: counter[x] % 2 == 1, counter) if len(s) % 2 == 1: if len(oddChars) == 1: mid = oddChars[0] counter[mid] -= 1 else: return [] elif len(oddChars) > 0: return [] for key in counter: ss += key * (counter[key] / 2) helper(sorted(ss), [], res, set()) for hword in res: ans.append(hword + mid + hword[::-1]) return ans
-
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 }