链接：https : //www.codechef.com/LRNDSA01/problems/LAPIN
程序描述： Lapindrome 被定义为一个字符串，当在中间分割时，给出两个具有相同字符和每个字符相同频率的一半。如果字符串中有奇数个字符，我们将忽略中间字符并检查 lapindrome。例如，gaga 是一个lapindrome，因为两半ga 和ga 具有相同频率的相同字符。此外，abccab、rotor 和 xyzxy 是一些 lapindromes 的例子。请注意，abbaab 不是跑步机。两半包含相同的字符，但它们的频率不匹配。你的任务很简单。给定一个字符串，你需要判断它是否是一个lapindrome。
我的代码：
#include <stdio.h>
#include <string.h>
int main(){
int i,t,len,j,k,arr_indx,check = 0;
char s[1000],left[500],right[500];
//s[] = input string
//left[] = left side of the string after division
//right[] = right side of the string after division
//len = length of the input string
//arr_index = It is the array index
scanf("%d",&t);
for(i = 1;i <= t;i++)
{
scanf("%s",&s);
len = strlen(s);
//if even length
if(len % 2 == 0)
{
for(j = 0;j < len/2;j++)
left[j] = s[j];
left[j] = '\0';
for(k = len/2,arr_indx = 0;k < len;k++,arr_indx++)
right[arr_indx] = s[k];
right[arr_indx] = '\0';
}
//if odd length
else
{
for(j = 0;j < len/2;j++)
left[j] = s[j];
left[j] = '\0';
for(k = ((len/2)+1),arr_indx = 0;k < len;k++,arr_indx++)
right[arr_indx] = s[k];
right[arr_indx] = '\0';
}
//Checking
for(k = 0;k < strlen(left);k++)
for(j = 0;j < strlen(right);j++)
if(left[k] == right[j])
check++;
if(check == strlen(left)) //printing
printf("YES\n");
else
printf("NO\n");
check = 0;
}
return 0;
}
您实现的算法既不正确又非常慢（即使它是正确的）。由于输入字符仅限于 a..z，您可以通过比较输入文本左右部分中字母的频率来实现快速算法。下面是一个示例实现。该代码假定 a..z 的字符代码是连续的，C 标准不保证这一点。
#include <stdio.h>
#include <string.h>
#define NLETTERS ('z' - 'a' + 1)
int main(void)
{
int T;
scanf("%d ", &T);
while (--T >= 0) {
char buf[1002];
int lfreq[NLETTERS] = {0}, rfreq[NLETTERS] = {0}, yes = 1;
fgets(buf, sizeof buf, stdin);
for (int i = 0, j = strcspn(buf, "\n") - 1; i < j; ++i, --j) {
++lfreq[buf[i] - 'a'];
++rfreq[buf[j] - 'a'];
}
for (int i = 0; i < NLETTERS; ++i) {
if (lfreq[i] != rfreq[i]) {
yes = 0;
break;
}
}
puts(yes ? "YES" : "NO");
}
return 0;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句