CodeForces 716B Complete the Word

题目链接:http://codeforces.com/problemset/problem/716/B

题目大意:

  给出一个字符串,判断其是否存在一个子串(满足:包含26个英文字母且不重复,字串中有‘?’表示占位符可表示字母),如果存在则输出该字串‘?’位置用替换后的字母代替,其他不在子串中的‘?’用字母代替即可。如果该字串不存在满足条件的子串,则输出-1.

举例:

----------------------------------

input
ABC??FGHIJK???OPQR?TUVWXY?
output
ABCDEFGHIJKLMNOPQRZTUVWXYS

------------

input
ABC??FGHIJK???OPQR?TUVWXY?WW??W
output
ABCDEFGHIJKLMNOPQRZTUVWXYSWWAAW

-------------

input
AABCDEFGHIJKLMNOPQRSTUVW??M
output
-1

--------------------------------------

解题思路:

  暴力即可。

  首先判断是否满足长度为26,<26 直接输出 -1.

否则:双重for 扫描,内循环每次从 i -> i+25 即可,如果 字符出现的个数+?的个数=26,则该子串满足,则记录左边的下标即可。

然后找出没有出现的字符,放在数组x[]。for循环,从记录下标开始-》下标+25,如果是‘?’,则用x[k++]代替‘?’。替换完子串‘?’,遍历整个字串,如果是‘?’用‘A’代替即可。

然后输出。

-->本次代码写low了。。。见谅。

AC Code:

 #include<bits/stdc++.h>
using namespace std;
const int N=+;
char ca[N];
int main()
{
int i,j; while(scanf("%s",ca)!=EOF)
{ if(strlen(ca)<)
{
printf("-1\n");
continue;
}
int cut,l,r,w;int dp[];
for(i=; i<strlen(ca); i++)
{
memset(dp,,sizeof(dp));
cut=w=l=r=;
for(j=i; j<i+; j++)
if(ca[j]=='?')w++;
else if(!dp[ca[j]]&&(int)ca[j]!=)
++cut,dp[ca[j]]=;
if(cut+w==)
{
l=i;
r=l+;
break;
}
}
if(r==)
{
printf("-1\n");
continue;
}
else
{
char s[],tem[];
int k=,x,w;
for(x=l; x<=l+; x++)
if(dp[ca[x]])s[k++]=ca[x];
k=;
for(x=; x<=; x++)
{
int flag=;
for(w=; w<strlen(s); w++)
{
if((int)s[w]-'A'==x)
{
flag=;
break;
}
}
if(flag)tem[k++]=(char)(x+'A');
}
k=;
for(x=l; x<=l+; x++)
if(ca[x]=='?')ca[x]=tem[k++];
for(i=; i<strlen(ca); i++)
if(ca[i]=='?')ca[i]='A';
puts(ca);
}
}
return ;
}
上一篇:psql的安装与数据库创建(ubuntu)


下一篇:C# 字符串加密解密函数