leetcode5. Longest Palindromic Substring的C实现

C语言 码拜 7年前 (2017-04-25) 1228次浏览
下面是本人用C实现的曼彻斯特算法用来解决最长回文子串问题,提交时出现 Runtime Error。
然后就拿系统给的Last executed input作Testcase,却又成功算出来了,并且跟expected answer一样。
真是不知道问题出在哪?麻烦各位高手给看看,代码如下:

char *expand(char *s)
{
	int i, j, len = strlen(s);
	char *str = (char *)malloc(sizeof(char) * (2 * len + 2));
	str[0] = "$";
	str[1] = "#";
	for(i = 0, j = 2; i < len; ++i)
	{
		str[j++] = s[i];
		str[j++] = "#";
	}
	str[j] = "\0";
	return str;
}
char* longestPalindrome(char* s) {
    char *str = expand(s);
	int len = strlen(str), max = 0, k, i, j;
	int p[2002] = {1, 1};
	int C = 1, R = 1;
	for(i = 2; i < len; ++i)
	{
		int i_mirror = C - (i - C);
		if(R - i > p[i_mirror])
			p[i] = p[i_mirror];
		else
			p[i] = R - i;
		while(str[i-p[i]-1] == str[i+p[i]+1])
			p[i]++;
		C = i;
		R = i + p[i];
	}
	for(i = 2; i < len; ++i)
		if(p[i] > max)
		{
			max = p[i];
			k = i;
		}
    char *sp = (char *)malloc(sizeof(char) * (len / 2));
	for(i = k - max + 1, j = 0; i < k + max; i += 2)
		sp[j++] = str[i];
	sp[j] = "\0";
	return sp;
}
解决方案

10

假如字符串为空,那么将会malloc 0 大小内存,而这是一个未定义行为

5

边界条件
输入输出格式
……

20

引用:
Quote: 引用:

假如字符串为空,那么将会malloc 0 大小内存,而这是一个未定义行为

也不行,刚才加了个if判断语句,还是卡在同样的testcase上

检查使用分配到的内存能否会越界
char *sp = (char *)malloc(sizeof(char) * (len / 2));
这句有没有考虑 len 为奇数的情况能否会越界
另外,动态分配的内存记得free是一个好的习惯


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明leetcode5. Longest Palindromic Substring的C实现
喜欢 (0)
[1034331897@qq.com]
分享 (0)