给定一个字符串数组strs,再给定两个字符串str1和str2,返回在strs中str1和str2的最小距离,如果str1或str2为null,或不在strs中,返回-1。
输入包含有多行,第一输入一个整数n,代表数组strs的长度,第二行有两个字符串分别代表str1和str2,接下来n行,每行一个字符串,代表数组strs (保证题目中出现的所有字符串长度均小于等于10)。
输出一行,包含一个整数,代表返回的值。
1 CD AB CD
-1
5 QWER 666 QWER 1234 qwe 666 QWER
1
时间复杂度,额外空间复杂度
#include <stdio.h> #include <string.h> #define MAXLEN 11 #define MAXN 100000 #define MIN(X, Y) ((X) < (Y) ? (X) : (Y)) int minDistance(char (*strs)[MAXLEN], int n, char *str1, char *str2); int main(void) { int n; char strs[MAXN][MAXLEN]; char str1[MAXLEN]; char str2[MAXLEN]; scanf("%d%s%s", &n, str1, str2); for (int i = 0; i < n; i++) { scanf("%s", strs[i]); } printf("%d\n", minDistance(strs, n, str1, str2)); return 0; } int minDistance(char (*strs)[MAXLEN], int n, char *str1, char *str2) { if (strlen(str1) == 0 || strlen(str2) == 0) return -1; if (strcmp(str1, str2) == 0) return 0; int pre1 = -1, pre2 = -1, res = -1; for (int i = 0; i < n; i++) { if (strcmp(strs[i], str1) == 0) { pre1 = i; if (pre2 != -1) res = res == -1 ? (i - pre2) : MIN(res, i - pre2); } if (strcmp(strs[i], str2) == 0) { pre2 = i; if (pre1 != -1) res = res == -1 ? (i - pre1) : MIN(res, i - pre1); } } return res; }