数组中两个字符串的最小距离

[编程题]数组中两个字符串的最小距离

热度指数：5588 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串数组strs，再给定两个字符串str1和str2，返回在strs中str1和str2的最小距离，如果str1或str2为null，或不在strs中，返回-1。

输入描述:

输入包含有多行，第一输入一个整数n，代表数组strs的长度，第二行有两个字符串分别代表str1和str2，接下来n行，每行一个字符串，代表数组strs (保证题目中出现的所有字符串长度均小于等于10)。

输出描述:

输出一行，包含一个整数，代表返回的值。

示例1

输入

1
CD AB
CD

输出

-1

示例2

输入

5
QWER 666
QWER
1234
qwe
666
QWER

输出

备注:

时间复杂度，额外空间复杂度

算法知识视频讲解

helloxuanbao

#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;
}

发表于 2022-02-08 18:32:48 回复(0)