267. Palindrome Permutation II
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Дана cadena s, return все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, return пустой список.
Ejemplo:
Input: s = "aabb"
Output: ["abba","baab"]
C# solución
coincidente/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++ solución
borrador automático, revisar antes de enviar#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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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)
}
}
}
}Algorithm
1️⃣
Проверка на возможность палиндромной перестановки:
Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s.
Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка
невозможна, и мы возвращаем пустой список.
2️⃣
Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.
3️⃣
Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли elementы перед свапом. Если да, то пропускаем данную перестановку.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.