資訊專欄INFORMATION COLUMN
Problem
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
ExampleGiven s = "aabb", return ["abba","baab"].
Given s = "abc", return [].
class Solution {
public List generatePalindromes(String s) {
List res = new ArrayList<>();
if (s == null || s.length() == 0) return res;
//create a map to record counts of chars: int[256]
//count the chars that have odd number of count: <= 1 means valid palindrome
int[] map = new int[256];
int odd = 0;
for (char ch: s.toCharArray()) {
map[ch]++;
if ((map[ch]&1) == 1) odd++;
else odd--;
}
if (odd > 1) return res;
//get mid string: should have length of 1 or 0
String mid = "";
int halfLen = 0;
for (int i = 0; i < 256; i++) {
if (map[i] > 0) {
//find the odd counted char, add to mid
if ((map[i]&1) == 1) {
mid += (char)i;
map[i]--;
}
//reduce count to half for each char
map[i] /= 2;
//update half palindrome length
halfLen += map[i];
}
}
dfs(map, "", mid, halfLen, res);
return res;
}
private void dfs(int[] map, String temp, String mid, int len, List res) {
if (temp.length() == len) {
StringBuilder sb = new StringBuilder(temp).reverse();
res.add(temp+mid+sb.toString());
return;
}
for (int i = 0; i < 256; i++) {
if (map[i] > 0) {
map[i]--;
dfs(map, temp+(char)i, mid, len, res);
map[i]++;
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/71518.html
摘要：判斷一個(gè)能否組成一個(gè)第一次出現(xiàn)增加一，第二次出現(xiàn)減少一。出現(xiàn)偶數(shù)次的最終對(duì)被抵消。出現(xiàn)基數(shù)詞的則會(huì)讓加一。類似于，奇數(shù)個(gè)的那個(gè)單獨(dú)考慮，必須放中間。得到各個(gè)字符一半數(shù)量的長(zhǎng)度數(shù)字的終止條件，利用的對(duì)稱性輸出結(jié)果。 Given a string s, return all the palindromic permutations (without duplicates) of it. R...
摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來(lái)判斷結(jié)果中是否有回文。而中心對(duì)稱點(diǎn)如果是字符，該字符會(huì)是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...
Problem Given a string, determine if a permutation of the string could form a palindrome. Example 1: Input: codeOutput: falseExample 2: Input: aabOutput: trueExample 3: Input: careracOutput: true Solu...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)懍F(xiàn)在翻起來(lái)覺(jué)得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒(méi)有按順序?qū)憽F(xiàn)在翻起來(lái)覺(jué)得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要：題目要求現(xiàn)在有一個(gè)字符串，將分割為多個(gè)子字符串從而保證每個(gè)子字符串都是回?cái)?shù)。我們只需要找到所有可以構(gòu)成回?cái)?shù)的并且得出最小值即可。即將字符作為，將字符所在的下標(biāo)列表作為。再采用上面所說(shuō)的方法，利用中間結(jié)果得出最小分割次數(shù)。 題目要求 Given a string s, partition s such that every substring of the partition is a ...
閱讀 3416·2023-04-26 00:58
閱讀 1319·2021-09-22 16:04
閱讀 3411·2021-09-02 15:11
閱讀 1627·2019-08-30 15:55
閱讀 2411·2019-08-30 15:55
閱讀 3486·2019-08-23 18:41
閱讀 3528·2019-08-23 18:18
閱讀 2802·2019-08-23 17:53
