[LeetCode] Palindrome Permutation II

简介: Problem Description: Given a string s, return all the palindromic permutations (without duplicates) of it.

Problem Description:

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Hint:

    1. If a palindromic permutation exists, we just need to generate the first half of the string.
    2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

As suggested by the first hint, we just need to get one half of the string (each character appears half the times in s), then generate all its unique permutations and concatenate them with the reversed half (possibly the single middle character if the length of the string s is odd).

All the above work will only be done if an palindrome permutation exists. To tell whether a palindrome permutation exists, Palindrome Permutation has paved the way for us. To generate all the unique permutations, you may as well refer to Permutations II or Next Permutation as suggested by the second hint. But I guess this part is not the main point of this problem, so I directly use the next_permutation of C++. Well, I am not quite whether this is the right way, but this gives shorter codes. Moreover, the tag of this problem is backtracking, which I guess only needs to be used in generating the permutations. After this is done, we can simply concatenate to make the palindromes.

The code is as follows.

 1 class Solution {
 2 public:
 3     vector<string> generatePalindromes(string s) {
 4         vector<string> palindromes;
 5         unordered_map<char, int> counts;
 6         for (char c : s) counts[c]++;
 7         int odd = 0; char mid; string half;
 8         for (auto p : counts) {
 9             if (p.second & 1) {
10                 odd++, mid = p.first;
11                 if (odd > 1) return palindromes;
12             }
13             half += string(p.second / 2, p.first);
14         }
15         palindromes = permutations(half);
16         for (string& p : palindromes) {
17             string t(p);
18             reverse(t.begin(), t.end());
19             if (odd) t = mid + t;
20             p += t;
21         }
22         return palindromes;
23     }
24 private: 
25     vector<string> permutations(string& s) {
26         vector<string> perms;
27         string t(s);
28         do {
29             perms.push_back(s);
30             next_permutation(s.begin(), s.end());
31         } while (s != t);
32         return perms;
33     }
34 };

 

目录
相关文章
LeetCode 409. Longest Palindrome
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
82 0
LeetCode 409. Longest Palindrome
|
索引
LeetCode 336. Palindrome Pairs
给定一组唯一的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。
142 0
LeetCode 336. Palindrome Pairs
|
算法 索引
LeetCode 214. Shortest Palindrome
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
94 0
LeetCode 214. Shortest Palindrome
|
canal
LeetCode 125. Valid Palindrome
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
94 0
LeetCode 125. Valid Palindrome
LeetCode 60. Permutation Sequence
集合[1,2,3,...,n]总共包含n的阶乘个独特的排列。
76 0
LeetCode 60. Permutation Sequence
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
Leetcode-Easy 234. Palindrome Linked List
Leetcode-Easy 234. Palindrome Linked List
60 0
Leetcode-Easy 234. Palindrome Linked List
【LeetCode】Palindrome Pairs(336)
  Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a   palindrome.
115 0
LeetCode之Palindrome Number(回文数)
LeetCode之Palindrome Number(回文数)
72 0
|
Java Python
LeetCode 234:回文链表 Palindrome Linked List
​请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? Follow up:Could you do it in O(n) time and O(1) space? 解题思路: 首先是寻找链表中间节点,这个可以用快慢指针来解决,快指针速度为2,慢指针速度为1,快指针遍历完链表时,慢指针刚好走到中间节点(相对)。
694 0