首页 > 试题广场 >

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

[编程题]数组中两个字符串的最小距离
  • 热度指数:4125 时间限制: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

输出

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

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