数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++ 语言
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学用 C++ 实现字符串中移除最少字符后组成回文排列
问题陈述
给定一个字符串 S，我们必须找出可以移除的最小字符数，从而使字符串 S 的任何排列成为回文串
示例
如果 str = “abcdba”，则我们移除 1 个字符，即‘c’或‘d’。
算法
1. There can be two types of a palindrome, even length, and odd length palindromes 2. We can deduce the fact that an even length palindrome must have every character occurring even number of times 3.An odd palindrome must have every character occurring even number of times except one character occurring odd number of time 4. Check the frequency of every character and those characters occurring odd number of times are then counted. Then the result is total count of odd frequency characters’ minus 1
示例
#include <bits/stdc++.h>
#define MAX 26
using namespace std;
int minCharactersRemoved(string str) {
int hash[MAX] = {0};
for (int i = 0; str[i]; ++i) {
hash[str[i] - 'a']++;
}
int cnt = 0;
for (int i = 0; i < MAX; ++i) {
if (hash[i] & 1) {
++cnt;
}
}
return (cnt == 0) ? 0 : (cnt - 1);
}
int main(){
string str = "abcdba";
cout << "Minimum characters to be removed = " <<
minCharactersRemoved(str) << endl;
return 0;
}编译并执行上述程序时，将生成以下输出
输出
Minimum characters to be removed = 1
更新于：2019 年 12 月 23 日
184 次查看
广告