讨论/题目交流/1055.形成字符串的最短路径,这个题目中有一个用例执行不过,特请教大家。/
1055.形成字符串的最短路径,这个题目中有一个用例执行不过,特请教大家。

使用c语言做的题目。

对于题目的这个用例:
"adbsc"
"addddddddddddsbc"

此用例在我本地执行OK

此用例在leetcode单独执行,也OK

在代码中增加了打印语句,打印了leetcode用例的输入参数,发现此leetcode用例的输入确实发生了变化,用例实际输入是:

“aaaaa ”
“aaaaaaaaaaaaa”

而用例本身应该输入是:

"adbsc"
"addddddddddddsbc"

共 2 个回复

代码都没有,怎么知道你错在哪。。。。。

代码如下,请指点,多谢。

#define CHAR_MAX_LENGTH 1001
int canBuildBySource(char* source, char* subTarget, int targetNum)
{
int findPos = 0;
int count = 0;
for (int i = 0; i < targetNum; i++) {
char tmpChar = subTarget[i];
for (int j = findPos; j < strlen(source); j++) {
if (tmpChar == source[j]) {
findPos = j + 1;
count++;
break;
}
}
}

if (count == targetNum) {
	return 1;
}

return 0;

}

int shortestWay(char * source, char * target)
{
printf("start source: %s \n", source);
printf("start target: %s \n", target);
int cost[CHAR_MAX_LENGTH];
memset(cost, 0, CHAR_MAX_LENGTH * sizeof(int));
int sourceLength = strlen(source);
int targetLength = strlen(target);

if (canBuildBySource(source, target, 1) == 0) {
	return -1;
}
else {
    cost[1] = 1;
}

for (int i = 1; i < targetLength; i++) {
	char subTarget[2];
    subTarget[0] = target[i - 1];
	subTarget[1] = target[i];
	if (canBuildBySource(source, subTarget, 2) == 1) {
		cost[i + 1] = cost[i];
	}
	else if (canBuildBySource(source, &subTarget[1], 1) == 1) {
		cost[i + 1] = cost[i] + 1;
	}
	else {
		return -1;
	}
}
printf("end source: %s \n", source);
printf("end target: %s \n", target);
return cost[targetLength];

}