首页 > 试题广场 >

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

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

热度指数：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

输出

备注:

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

算法知识视频讲解

H.T.W

public class Main { public static void main(String[] args) {
        Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt();
            String s1 = in.next();
            String s2 = in.next();
            String s; int result = -1; int cursor1 = -1, cursor2 = -1; for (int i = 0; i < n; ++ i) {
                s = in.next(); if (s1.equals(s)) {
                    cursor1 = i; if (cursor2 != -1) {
                        result = result == -1 ? cursor1 - cursor2 : Math.min(result, cursor1 - cursor2);
                    }
                } if (s2.equals(s)) {
                    cursor2 = i; if (cursor1 != -1) {
                        result = result == -1 ? cursor2 - cursor1 : Math.min(result, cursor2 - cursor1);
                    }
                }
            }
            System.out.println(result);
        }
    }

编辑于 2020-01-15 19:50:30 回复(1)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,res1=-1,res2=-1,res=INT_MAX;
    cin>>n;
    vector<string>str(n);
    string str1,str2;
    cin>>str1>>str2;
    for(int i=0;i<n;i++)
        cin>>str[i];
    for(int i=0;i<n;i++)
    {
        if(str[i]==str1)
        {
            res1=i;
            if(res2!=-1)
                res=min(res,abs(res1-res2));
        }
        else if(str[i]==str2)
        {
            res2=i;
            if(res1!=-1)
                res=min(res,abs(res1-res2));
        }
    }
    if(res1==-1||res2==-1)
        cout<<-1<<endl;
    else
        cout<<res<<endl;
    return 0;
}

发表于 2019-09-22 14:17:23 回复(0)

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)

Java

jahentao

O(N)的时间复杂度，从左往右扫一遍，空间复杂度O(1)

扫到了记录last1和last2分别表示str1和str2最近出现的下标，那么i - last1或i - last2就是最短的距离，一直更新这个最短距离。

import java.util.*;

public class Main {
    public static int process(String[] strs, String str1, String str2) {
        if (str1 == null || str2 == null) {
            return -1;
        }
        int last1 = -1, last2 = -1, min = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals(str1)) {
                min = last2 == -1 ? min : Math.min(min, i - last2);
                last1 = i;
            } else if (strs[i].equals(str2)) {
                min = last1 == -1 ? min : Math.min(min, i - last1);
                last2 = i;
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str1 = sc.next();
        String str2 = sc.next();
        String[] strs = new String[n];
        for (int i = 0; i < n; i ++) {
            strs[i] = sc.next();
        }
        sc.close();
        int res = process(strs, str1, str2);
        System.out.println(res);
    }
}

发表于 2020-06-02 20:22:27 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, Min=INT_MAX, l=-1, r=-1;
    cin>>n;
    string s1, s2, s;
    cin>>s1>>s2;
    for(int i=0;i<n;i++){
        cin>>s;
        if(s == s1){
            l = i;
            if(r != -1)
                Min = min(Min, abs(r-l));
        }else if(s == s2){
            r = i;
            if(l != -1)
                Min = min(Min, abs(r-l));
        }
    }
    if(l==-1 || r==-1)
        cout<<-1<<endl;
    else
        cout<<Min<<endl;
    return 0;
}

发表于 2020-05-05 08:22:27 回复(0)

C++

S_hh

#include <iostream>

#include<math.h>

using namespace std;

int main() {

int n;

string str1, str2;

cin >> n;

cin>>str1>>str2;

int pre1=-1,pre2=-1,ret=0X3f3f3f;

string s;

for(int i=0;i<n;i++){

cin>>s;

if(s==str1)pre1=i;

else if(s==str2)pre2=i;

if(pre1!=-1&&pre2!=-1){

ret=min(ret,abs(pre1-pre2));

}

if(pre1==-1||pre2==-1)cout<<"-1"<<endl;

else

cout<<ret<<endl;

}

发表于 2024-09-08 15:29:44 回复(0)

日刷百题

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
int n;
string str1, str2;
cin >> n; // Read n first before initializing strs
vector<string> strs(n); // Initialize strs with the correct size n
cin >> str1 >> str2;

for (int i = 0; i < n; i++) {
cin >> strs[i];
}

if (str1.empty() || str2.empty()) {
cout << -1 << endl;
return 0;
}

int end1 = -1;
int end2 = -1;
int len = 0x3f3f3f;
for (int i = 0; i < n; i++) {
if (strs[i] == str1) {
end1 = i;
if (end2 != -1) {
len = min(len, abs(end1 - end2));
}
} else if (strs[i] == str2) {
end2 = i;
if (end1 != -1) {
len = min(len, abs(end1 - end2));
}
}
}

if (end1 == -1 || end2 == -1) {
cout << -1 << endl;
} else {
cout << len << endl;
}

return 0;
}

发表于 2024-07-08 11:38:17 回复(0)

C/C++

求实习的四郎很积极

#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
#define int long long
using namespace std;
string str1, str2, strs;
int ans = 0x3f3f3f3f3f3f3f3f;
int n;
vector<string> vs;
void solve()
{
    cin >> n;
    cin >> str1 >> str2;
    for(int i = 0; i < n; ++i)
    {
        cin >> strs;
        vs.push_back(strs);        
    }

    int prev1 = -1; // QWER
    int prev2 = -1; // 666
    for(int i = 0; i < n; ++i)
    {
        if(vs[i] == str1)
        {
            prev1 = i;
            if(prev2 != -1)
                ans = min(ans, prev1 - prev2);
        }
        else if(vs[i] == str2)
        {
            prev2 = i;
            if(prev1 != -1)
                ans = min(ans, prev2 - prev1);
        }
    }
    if (prev1 == -1 || prev2 == -1)
    {
        cout << -1 << endl;
    }
    else
        cout << ans << endl;

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

编辑于 2024-04-18 20:40:13 回复(0)

111无与伦比

import java.util.*; 
import java.io.*;
public class Main{
public static void main(String[] args) throws Throwable {
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(reader.readLine());
String[] str=reader.readLine().split(" ");
String s1=str[0];
String s2=str[1];
int prev1=-1;//存储i下标前面，s1对应的下标
int prev2=-1;//存储i下标前面，s2对应的下标
int ret=0x3f3f3f3f;
for(int i=0;i<n;i++){
    String s=reader.readLine();
    if(s.equals(s1)){//去前面找最近的s2
    prev1=i;
        if(prev2!=-1){
            ret=Math.min(ret,i-prev2);
        }
    }
    else if(s.equals(s2)){
        prev2=i;
        if(prev1!=-1){
            ret=Math.min(ret,i-prev1);
        }
    }
}
System.out.println(ret==0x3f3f3f3f?-1:ret);
}
}

发表于 2024-04-18 16:28:43 回复(0)

C/C++

MikeJone

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    int xia1 = 0;
    int xia2 = 0;
    int ans = 1e8;
    for (int i = 1; i <= n; i++)
    {
        string strs;
        cin >> strs;
        if (strs == s1)
        {
            xia1 = i;
        }

        if (strs == s2)
        {
            xia2 = i;
        }
        if (xia1 != 0 && xia2 != 0)
        {
            ans = min(abs(xia1 - xia2), ans);
        }
        
    }

    if (ans == 1e8)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans;
    }
    return 0;
}

发表于 2024-04-18 12:54:52 回复(0)

冰狗Y

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNext()) {

int n = in.nextInt();

String s1 = in.next();

String s2 = in.next();

int cursor1 = -1; // 记录字符串 s1 的位置

int cursor2 = -1; // 记录字符串 s2 的位置

int result = -1;// 存储最小差值，默认为 -1

for (int i = 0; i < n; ++i) {

String s = in.next();

if (s1.equals(s)) {

cursor1 = i;

if (cursor2 != -1) {

int currentDiff = cursor1 - cursor2;

if (result == -1 || currentDiff < result) {

result = currentDiff;

}

if (s.equals(s2)) {

cursor2 = i;

if (cursor1 != -1) {

int currentDiff = cursor2 - cursor1;

if (result == -1 || currentDiff < result) {

result = currentDiff;

}

} System.out.println(result);

}

发表于 2023-07-01 21:06:02 回复(0)

Java

眼睛想旅行121

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] data=br.readLine().split(" ");
        String str1=data[0];
        String str2=data[1];
        String[]strs=new String[n];
       for (int i = 0; i <n; i++) {
            strs[i]=br.readLine();
        }
            int res = minDistance(strs, str1, str2);
            System.out.println(res);
        }
    
    public static int minDistance(String[]strs,String str1,String str2){
        if(str1==null||str2==null){
            return -1;
        }
        if(str1.equals(str2)){
            return 0;
        }
        int last1=-1;
        int last2=-1;
        int min=Integer.MAX_VALUE;
        for(int i=0; i<strs.length; i++){
            if(strs[i].equals(str1)){
                min=Math.min(min,last2==-1?min:i-last2);
                last1=i;
            }
            if(strs[i].equals(str2)){
                min=Math.min(min,last1==-1?min:i-last1);
                last2=i;
            }
        }
        return min==Integer.MAX_VALUE?-1:min;
    }
 }

发表于 2021-03-30 15:40:19 回复(0)

别搁那忽悠人了


	#include <iostream>
(720)#include <string>
#include <vector>
using namespace std;



	int main()
{
    int n;
    cin >> n;
    
    string l,s;
    cin >> l >> s;
    
    vector<string> str(n);
    for (int i = 0;i < n;i++){
        cin >> str[i];
        
    }
    
    int last1 = -1,last2 = -1;
    int Min = n;
    for (int i = 0;i < n;i++){
        if (str[i] == l){
            last1 = i;
            if (last2 != -1){
                Min = min(abs(last2 - last1),Min);
            }
            
        }
        else if (str[i] == s){
            last2 = i;
            if (last1 != -1){
                Min = min(abs(last2 - last1),Min);
            }
        }
        else{
            continue;
        }
        
        
    }
    if ((last1 == -1)||(last2 == -1)){
        cout << -1 << endl;
    }



	        cout << Min << endl;



	    return 0;
    
}

发表于 2020-05-10 18:39:44 回复(0)

復活の検事

import java.util.Scanner;
import java.util.regex.Matcher;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int len = scanner.nextInt();
            String str1 = scanner.next();
            String str2 = scanner.next();
            String[] str = new String[len];
            for(int i=0;i<len;i++){
                str[i] = scanner.next();
            }
            System.out.println(getDistance(str, str1, str2));
        }
    }

    public static int getDistance(String[] str, String str1, String str2){
        if(str1 == null || str2 == null){
            return -1;
        }
        if(str1.equals(str2)){
            return 0;
        }
        // 最近一次出现str1的位置
        int last1 = -1;
        // 最近一次出现str2的位置
        int last2 = -1;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<str.length;i++){
            if(str[i].equals(str1)){
                min = Math.min(min, last2 == -1 ? min : i-last2);
                last1 = i;
            }
            if(str[i].equals(str2)){
                min = Math.min(min, last1 == -1 ? min :  i-last1);
                last2 = i;
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }



}

发表于 2020-05-07 13:11:59 回复(0)

包子冲汤胡辣汤

#include<cstdio>
(802)#include<iostream>
#include<string>
(765)#include<cmath>
using namespace std;
int main(){
    int n;
    string s1,s2,s;
    scanf("%d",&n);
    cin>>s1>>s2;
    int dis=100010;
    int k1=-1,k2=-1;
    for(int i=0;i<n;++i){
        cin>>s;
        if(s==s1)
            k1=i;
        if(s==s2)
            k2=i;
        if(k1!=-1&&k2!=-1&&dis>abs(k2-k1)){
            dis=abs(k2-k1);
        }
    }
    if(dis==100010)
        printf("-1");
    else{
        printf("%d",dis);
    }
    return 0;
}

发表于 2020-03-25 17:07:06 回复(0)

红玉圆

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

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

/*思路：遍历str数组，初始距离为整个str长度。若元素与str1相同，则从此开始向后遍历寻找str2，找到后比较距离，若小于目前距离则更新；反之判断若元素与str2相同，则从此开始向后遍历寻找str1，找到后比较距离，若小于目前距离则更新。其中若距离为1已经是目前最小，直接输出*/

#include <iostream>
#include<string>
#include<string.h>

using namespace std;

int main(int argc, char** argv)
{
    int len;
    cin >> len;
    string str1, str2;
    cin >> str1 >> str2;
    if (str1 == "" || str2 == "")//判断是否str1，str2为空
    {
        cout<<"-1";
        return 0;
    }
    if (str1 == str2)//若str1=-str2，距离为0
    {
        cout << "0";
        return 0;
    }
    string *str = new string[len];
    for (int i = 0; i < len; i++)
    {
        cin >> str[i];
    }

    int dis=len;
    for (int i = 0; i < len; i++)
    {
        if (str1 == str[i])
        {
            for (int j = i + 1; j < len; j++)
            if (str2 == str[j])
            if (dis > j - i)
                dis = j - i;
        }
        else if (str2 == str[i])
        {
            for (int j = i + 1; j < len; j++)
            if (str1 == str[j])
            if (dis > j - i)
                dis = j - i;
        }
        if (dis == 1) break;//若str1、-str2距离为1则直接输出
    }
    if (dis == len) cout << "-1" << endl;//距离为len代表二者至少有一个不在str中
    else cout<<dis<<endl;
    return 0;
    system("pause");

}

发表于 2019-10-15 23:52:37 回复(0)

圣诞节的安徒生

#自定义函数求两个字符串在字符串数组中的最短距离
def Minlength(str1,str2,strs):
    if str1.isspace()==True or len(str2)==0 or str1 not in strs or str2 not in strs:
        return -1
    #存放两个字符串在字符串数组中的索引
    index1 = []
    index2 = []
    for i in range(len(strs)):
        if str1 == strs[i]:
            index1.append(i)
        elif str2 == strs[i]:
            index2.append(i)
    #最短距离初始化为字符串数组的长度
    minlength = len(strs)
    for i in index1:
        for j in index2:
            if abs(i-j) < minlength:
                minlength = abs(i-j)
    return minlength
#接收输入
n = eval(input())
str1,str2 = input().split()
strs = []
for i in range(n):
    strs.append(input())
print(Minlength(str1,str2,strs))

发表于 2019-08-12 10:21:05 回复(0)

提交观点

问题信息

字符串模拟

上传者：小小

难度：

17条回答 55收藏 7701浏览

通过挑战的用户

查看代码

激进的小菜鸡

2023-03-10 17:30:31
牛客32358...

2023-02-17 18:52:32
追风少年小曾

2023-02-05 15:21:37
Tangeri...

2023-01-12 14:29:19
勉为其难201...

2022-12-18 17:20:54

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

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题