专栏首页Michael阿明学习之路LeetCode 267. 回文排列 II(回溯)

LeetCode 267. 回文排列 II(回溯)

文章目录

1. 题目

给定一个字符串 s ,返回其通过重新排列组合后所有可能的回文字符串,并去除重复的组合。

如不能形成任何回文排列时,则返回一个空列表。

示例 1:
输入: "aabb"
输出: ["abba", "baab"]

示例 2:
输入: "abc"
输出: []

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/palindrome-permutation-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 对字符进行计数,判断能否生成回文串
  • 然后把奇数个的1个字符放中间,回溯在字符两侧放一对相同的字符
class Solution {
	vector<string> ans;
	int n;
public:
    vector<string> generatePalindromes(string s) {
        vector<int> count(128,0);
        n = s.size();
        for(char ch : s)
        	count[ch]++;
        int odd = 0, idx;
        for(int i = 0; i < 128; ++i)
        {
        	if(count[i]&1)
        	{
        		odd++;
        		idx = i;
        	}
        	if(odd > 1)
        		return {};
        }
        s = odd ? string(1, idx) : "";
        odd ? count[idx]-- : 0;//奇数的字符-1
        dfs(count,s);
        return ans;
    }

    void dfs(vector<int>& count, string s)
    {
    	if(s.size()==n)
    	{
    		ans.push_back(s);//长度够了返回
    		return;
    	}
    	for(int i = 0; i < 128; ++i)
    	{
    		if(count[i])
    		{
    			count[i] -= 2;//两侧加上相同字符,还是回文
    			dfs(count, char(i)+s+char(i));
    			count[i] += 2;//回溯
    		}
    	}
    }
};

4 ms 6.9 MB 我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2bs1ihf8vfpcc

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1481. 不同整数的最少数目(计数+排序+贪心)

    给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素,请找出移除后数组中不同整数的最少数目。

    Michael阿明
  • LeetCode 686. 重复叠加字符串匹配

    给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。

    Michael阿明
  • LeetCode 1093. 大样本统计

    我们对 0 到 255 之间的整数进行采样,并将结果存储在数组 count 中:count[k] 就是整数 k 的采样个数。

    Michael阿明
  • LeetCode 1481. 不同整数的最少数目(计数+排序+贪心)

    给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素,请找出移除后数组中不同整数的最少数目。

    Michael阿明
  • PAT Basic 1007

    chain
  • Replace方法与正则表达式的性能比较

    今天做项目时遇到一个小需求:要将字符串中的回车符号替换成其它符号(比如"<br/>")。 考虑到不同的情况下,有些系统中是用\r\n作回车符,有些仅用\n就代表...

    菩提树下的杨过
  • 『Demo』你想开发的页面特效,这里都能找到~

    来源 | 微信小程序联盟 作者 | 极乐蜀黍 这期极乐大叔将小程序内各种页面效果实现方法聚合了一下,以便大家能够迅速而方便的使用。 1 文字跑马灯效果: h...

    极乐君
  • hihoCoder #1015 : KMP算法【KMP裸题,板子】

    #1015 : KMP算法 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程...

    Angel_Kitty
  • 运维必备技能 WEB 日志分析

    文章节选自《Netkiller Monitoring 手札》 20.2. Web 20.2.1. Apache Log 1、查看当天有多少个IP访问: awk ...

    netkiller old
  • LeetCode 210. Course Schedule II(拓扑排序)

    和这道题目一样:https://www.cnblogs.com/dacc123/p/12306344.html

    ShenduCC

扫码关注云+社区

领取腾讯云代金券