267. Palindrome Permutation II
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Дана chuỗi s, return все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, return пустой список.
Ví dụ:
Input: s = "aabb"
Output: ["abba","baab"]
C# lời giải
đã khớp/gốcusing 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcimport 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcpackage 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ы перед свапом. Если да, то пропускаем данную перестановку.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.