Java教程

267:回文序列II

本文主要是介绍267:回文序列II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
查看代码
//将原生解法转化为ACM解法的一个例子
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int n;
vector<string>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;//回溯
		}
	}
}
int main() {
	string s ;
	cin >> 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);
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}
这篇关于267:回文序列II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!