[搜狗] 找一个字符串中包含全部出现字符的最小字符串

简介: 一个字符串中含有n个字符,其中有m个不同的字符,n>>m,用最少的时间和空间找到包含所有这m个字符的最短的字串,不考虑特殊字符,只考虑字母数字即可。例如: abccbaddac,返回:cbad aabcadbbbcca,返回:bcad 实现代码: #include <iostream>using namespace std;void Search(cha
一个字符串中含有n个字符,其中有m个不同的字符,n>>m,用最少的时间和空间找到包含所有这m个字符的最短的字串,不考虑特殊字符,只考虑字母数字即可。

例如:

abccbaddac,返回:cbad

aabcadbbbcca,返回:bcad

实现代码:

#include <iostream>
using namespace std;
void Search(char input[], char output[]);
int main()
{
	char* input = "abccbaddac";
	char* output = new char[strlen(input)];
	Search(input,output);
	cout<<output<<endl;
}

void Search(char input[], char output[])
{
	bool num[10] = {0}; //数字字符
	bool small[26] = {0}; //小写字符
	bool big[26] = {0}; //大写字符
	int sum = 0; //不同字符的个数
	int temp, index;
	for (int i = 0; i < strlen(input); i++)
	{
		temp = input[i];
		if (temp >= 97)
		{
			index = input[i] - 'a';
			if (small[index] == 0)
			{
				small[index] = 1;
				sum++;
			}
		}
		else if (temp <= 57)
		{
			index = input[i] - '0';
			if (num[index] == 0)
			{
				num[index] = 1;
				sum++;
			}
		}
		else
		{
			index = input[i] - 'A';
			if (big[index] == 0)
			{
				big[index] = 1;
				sum++;
			}
		}
	}

	bool t_num[10] = {0}; //数字字符
	bool t_small[26] = {0}; //小写字符
	bool t_big[26] = {0}; //大写字符
	int t_sum = 0;

	int min = strlen(input);
	char* out = new char[strlen(output) + 1];
	memset(out,0,sizeof(out));

	for (int i = 0; i < strlen(input); i++)
	{
		char* pout = out;
		t_sum = 0;
		memset(t_num,0,sizeof(t_num));
		memset(t_small,0,sizeof(t_small));
		memset(t_big,0,sizeof(t_big));
		int j = i;
		while(j < strlen(input))
		{
			*pout++ = input[j];
			temp = input[j];
			if (temp >= 97)
			{
				index = input[j] - 'a';
				if (t_small[index] == 0)
				{
					t_small[index] = 1;
					t_sum++;
				}
			}
			else if (temp <= 57)
			{
				index = input[j] - '0';
				if (t_num[index] == 0)
				{
					t_num[index] = 1;
					t_sum++;
				}
			}
			else
			{
				index = input[j] - 'A';
				if (t_big[index] == 0)
				{
					t_big[index] = 1;
					t_sum++;
				}
			}
			if (t_sum == sum)
			{
				int len = j - i;
				if(min > len)
				{
					min = len;
					*pout = '\0';
					strcpy(output,out);
					j = i + len - sum;
					break;
				}
			}
			j++;
		}
	}
	delete [] out;
}

目录
相关文章
|
24天前
|
索引 容器
06-数据容器str(字符串)-字符串的下标索引/字符串无法修改/查找字符串下标初始值/字符串的替换/字符串的分割/字符串去除前后空格/统计字符串的数量/字符串的循环遍历/对字符串进行分割
06-数据容器str(字符串)-字符串的下标索引/字符串无法修改/查找字符串下标初始值/字符串的替换/字符串的分割/字符串去除前后空格/统计字符串的数量/字符串的循环遍历/对字符串进行分割
|
2月前
字符串,每个里面包含0-N个数字,如3,8,2,编写函数,将两个这样的字符串合并,并且输出的字符串里面没有重复的数字,并从大到小排列.
字符串,每个里面包含0-N个数字,如3,8,2,编写函数,将两个这样的字符串合并,并且输出的字符串里面没有重复的数字,并从大到小排列.
21 0
|
5月前
|
算法 测试技术 C#
C++算法:包含三个字符串的最短字符串
C++算法:包含三个字符串的最短字符串
|
7月前
题目:下列给定程序中函数fun的功能是:从p所指字符串中找出ASCII码值最大的字符,将其放在第一个位置上,并将该字符前的原字符向后顺序移动。
题目:下列给定程序中函数fun的功能是:从p所指字符串中找出ASCII码值最大的字符,将其放在第一个位置上,并将该字符前的原字符向后顺序移动。
|
12月前
|
数据安全/隐私保护 索引
labview字符串数据长度连接子字符串大小写替换删除插入日期匹配
labview字符串数据长度连接子字符串大小写替换删除插入日期匹配
117 0
|
12月前
|
iOS开发
iOS 检测字符串中数字个数、特殊符号个数
iOS 检测字符串中数字个数、特殊符号个数
138 0
|
人工智能 BI
762 字符串匹配----给定两个长度相同的字符串 a 和字符串 b。如果在某个位置 i 上,满足字符串 a 上的字符 a[i] 和字符串 b 上的字符 b[i] 相同,那么这个位置上的字符就是匹配
给定两个长度相同的字符串 aa 和字符串 bb。 如果在某个位置 ii 上,满足字符串 aa 上的字符 a[i]a[i] 和字符串 bb 上的字符 b[i]b[i] 相同,那么这个位置上的字符就是匹配的。 如果两个字符串的匹配位置的数量与字符串总长度的比值大于或等于 kk,则称两个字符串是匹配的。
210 0
有一个字符串,其中包含中文字符、英文字符和数字字符,请统计和打印出各个字符的个数
有一个字符串,其中包含中文字符、英文字符和数字字符,请统计和打印出各个字符的个数
255 0
C#编程-17:字符串取第一个和最后一个字符
C#编程-17:字符串取第一个和最后一个字符
264 0