267. Palindrome Permutation II
leetcode medium
#array#csharp#hash-table#leetcode#medium#string
Task
Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.
Пример:
Input: s = "aabb"
Output: ["abba","baab"]
C# solution
matched/originalusing System;
using System.Collections.Generic;
using System.Text;
public class Solution {
private HashSet<string> set;
public Solution() {
set = new HashSet<string>();
}
public IList<string> GeneratePalindromes(string s) {
int[] map = new int[128];
char[] st = new char[s.Length / 2];
if (!CanPermutePalindrome(s, map)) {
return new List<string>();
}
char ch = '\0';
int k = 0;
for (int i = 0; i < map.Length; i++) {
if (map[i] % 2 == 1) {
ch = (char)i;
}
for (int j = 0; j < map[i] / 2; j++) {
st[k++] = (char)i;
}
}
Permute(st, 0, ch);
return new List<string>(set);
}
private bool CanPermutePalindrome(string s, int[] map) {
int count = 0;
foreach (char c in s) {
int index = (int)c;
map[index]++;
if (map[index] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
private void Swap(ref char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
private void Permute(char[] s, int l, char ch) {
if (l == s.Length) {
StringBuilder sb = new StringBuilder();
sb.Append(s);
if (ch != '\0') {
sb.Append(ch);
}
Array.Reverse(s);
sb.Append(s);
set.Add(sb.ToString());
Array.Reverse(s);
} else {
for (int i = l; i < s.Length; i++) {
if (s[l] != s[i] || l == i) {
Swap(ref s, l, i);
Permute(s, l + 1, ch);
Swap(ref s, l, i);
}
}
}
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private HashSet<string> set;
public Solution() {
set = new HashSet<string>();
}
public vector<string> GeneratePalindromes(string s) {
vector<int>& map = new int[128];
char[] st = new char[s.size() / 2];
if (!CanPermutePalindrome(s, map)) {
return new List<string>();
}
char ch = '\0';
int k = 0;
for (int i = 0; i < map.size(); i++) {
if (map[i] % 2 == 1) {
ch = (char)i;
}
for (int j = 0; j < map[i] / 2; j++) {
st[k++] = (char)i;
}
}
Permute(st, 0, ch);
return new List<string>(set);
}
private bool CanPermutePalindrome(string s, vector<int>& map) {
int count = 0;
foreach (char c in s) {
int index = (int)c;
map[index]++;
if (map[index] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
private void Swap(ref char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
private void Permute(char[] s, int l, char ch) {
if (l == s.size()) {
StringBuilder sb = new StringBuilder();
sb.Append(s);
if (ch != '\0') {
sb.Append(ch);
}
Array.Reverse(s);
sb.Append(s);
set.push_back(sb.ToString());
Array.Reverse(s);
} else {
for (int i = l; i < s.size(); i++) {
if (s[l] != s[i] || l == i) {
Swap(ref s, l, i);
Permute(s, l + 1, ch);
Swap(ref s, l, i);
}
}
}
}
}Java solution
matched/originalimport java.util.*;
public class Solution {
private Set<String> set;
public Solution() {
set = new HashSet<>();
}
public List<String> generatePalindromes(String s) {
int[] map = new int[128];
char[] st = new char[s.length() / 2];
if (!canPermutePalindrome(s, map)) {
return new ArrayList<>();
}
char ch = '\0';
int k = 0;
for (int i = 0; i < map.length; i++) {
if (map[i] % 2 == 1) {
ch = (char) i;
}
for (int j = 0; j < map[i] / 2; j++) {
st[k++] = (char) i;
}
}
permute(st, 0, ch);
return new ArrayList<>(set);
}
private boolean canPermutePalindrome(String s, int[] map) {
int count = 0;
for (char c : s.toCharArray()) {
int index = (int) c;
map[index]++;
if (map[index] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
private void swap(char[]JavaScript solution
matched/originalclass Solution {
constructor() {
this.set = new Set();
}
generatePalindromes(s) {
const map = new Array(128).fill(0);
const st = new Array(Math.floor(s.length / 2)).fill('');
if (!this.canPermutePalindrome(s, map)) {
return [];
}
let ch = '';
let k = 0;
for (let i = 0; i < map.length; i++) {
if (map[i] % 2 === 1) {
ch = String.fromCharCode(i);
}
for (let j = 0; j < Math.floor(map[i] / 2); j++) {
st[k++] = String.fromCharCode(i);
}
}
this.permute(st, 0, ch);
return Array.from(this.set);
}
canPermutePalindrome(s, map) {
let count = 0;
for (const char of s) {
const index = char.charCodeAt(0);
map[index]++;
if (map[index] % 2 === 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
swap(s, i, j) {
[s[i], s[j]] = [s[j], s[i]];
}
permute(s, l, ch) {
if (l === s.length) {
this.set.add(s.join('') + (ch === '' ? '' : ch) + s.slice().reverse().join(''));
} else {
for (let i = l; i < s.length; i++) {
if (s[l] !== s[i] || l === i) {
this.swap(s, l, i);
this.permute(s, l + 1, ch);
this.swap(s, l, i);
}
}
}
}
}Python solution
matched/originalclass Solution:
def __init__(self):
self.set = set()
def generatePalindromes(self, s: str) -> list[str]:
map = [0] * 128
st = [''] * (len(s) // 2)
if not self.canPermutePalindrome(s, map):
return []
ch = ''
k = 0
for i in range(len(map)):
if map[i] % 2 == 1:
ch = chr(i)
for j in range(map[i] // 2):
st[k] = chr(i)
k += 1
self.permute(st, 0, ch)
return list(self.set)
def canPermutePalindrome(self, s: str, map: list[int]) -> bool:
count = 0
for char in s:
index = ord(char)
map[index] += 1
if map[index] % 2 == 0:
count -= 1
else:
count += 1
return count <= 1
def swap(self, s: list[str], i: int, j: int) -> None:
s[i], s[j] = s[j], s[i]
def permute(self, s: list[str], l: int, ch: str) -> None:
if l == len(s):
self.set.add(''.join(s) + (ch if ch != '' else '') + ''.join(s[::-1]))
else:
for i in range(l, len(s)):
if s[l] != s[i] or l == i:
self.swap(s, l, i)
self.permute(s, l + 1, ch)
self.swap(s, l, i)Go solution
matched/originalpackage main
import (
"fmt"
"strings"
)
type Solution struct {
set map[string]struct{}
}
func NewSolution() *Solution {
return &Solution{set: make(map[string]struct{})}
}
func (sol *Solution) generatePalindromes(s string) []string {
mapChars := make([]int, 128)
st := make([]rune, len(s)/2)
if !sol.canPermutePalindrome(s, mapChars) {
return []string{}
}
var ch rune
k := 0
for i := 0; i < len(mapChars); i++ {
if mapChars[i]%2 == 1 {
ch = rune(i)
}
for j := 0; j < mapChars[i]/2; j++ {
st[k] = rune(i)
k++
}
}
sol.permute(st, 0, ch)
result := []string{}
for key := range sol.set {
result = append(result, key)
}
return result
}
func (sol *Solution) canPermutePalindrome(s string, mapChars []int) bool {
count := 0
for _, char := range s {
index := int(char)
mapChars[index]++
if mapChars[index]%2 == 0 {
count--
} else {
count++
}
}
return count <= 1
}
func (sol *Solution) swap(s []rune, i, j int) {
s[i], s[j] = s[j], s[i]
}
func (sol *Solution) permute(s []rune, l int, ch rune) {
if l == len(s) {
var sb strings.Builder
sb.WriteString(string(s))
if ch != 0 {
sb.WriteRune(ch)
}
for i := len(s) - 1; i >= 0; i-- {
sb.WriteRune(s[i])
}
sol.set[sb.String()] = struct{}{}
} else {
for i := l; i < len(s); i++ {
if s[l] != s[i] || l == i {
sol.swap(s, l, i)
sol.permute(s, l+1, ch)
sol.swap(s, l, i)
}
}
}
}Explanation
Algorithm
1️⃣
Проверка на возможность палиндромной перестановки:
Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s.
Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка
невозможна, и мы возвращаем пустой список.
2️⃣
Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.
3️⃣
Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.
😎