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

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

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

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

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

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

#include <iostream>
#include <cmath>
using namespace std;

const int N = 1e5 + 10;
string a[N];
int main()
{
    int n; cin >> n;
    string s1, s2; cin >> s1 >> s2;
    int l = 0, r = 0;
    int ret = 0x3f3f3f3f;
    for(int i = 0; i < n; i++) 
    {
        cin >> a[i];
        if(a[i] == s1) l = i;
        if(a[i] == s2) r = i;
        if(l != 0 && r != 0)
        ret = min(ret, abs(l - r));
    }
    if(ret == 0x3f3f3f3f) cout << -1 << endl;
    else
    cout << ret << endl;

    return 0;
}

package main

import (
	"fmt"
	"math"
)

func main() {
	var n int = 0
	fmt.Scan(&n)
	var str1, str2 string
	fmt.Scan(&str1, &str2)
	var strs = []string{}
	for i := 0; i < n; i++ {
		var tempstr string
		fmt.Scan(&tempstr)
		strs = append(strs, tempstr)
	}

	var result int = math.MaxInt64

	var index1 int = -1
	var index2 int = -1
	for i := 0; i < len(strs); i++ {
		if strs[i] == str1 {
			index1 = i
			if index2 != -1 {
				result = int(math.Min(math.Abs(float64(index1-index2)), float64(result)))
			}
		} else if strs[i] == str2 {
			index2 = i
			if index1 != -1 {
				result = int(math.Min(math.Abs(float64(index1-index2)), float64(result)))
			}
		}
	}
	if result == math.MaxInt64 {
		fmt.Println(-1)
	} else {
		fmt.Println(result)
	}
}

贪心，获取插入时的序号差

#include 
#include 
#include 
using namespace std;
int main() 
{
    int n;
    int prevstr1 = 0, prevstr2 = 0;
    int result = 0x3f3f3f3f;
    string str1, str2, strs;
    cin >> n;
    cin >> str1 >> str2;
    while(n)
    {
        cin >> strs;
        if(strs == str1)
            prevstr1 = n;
        else if(strs == str2)
            prevstr2 = n;
        if(prevstr1 && prevstr2)
            result = min(result, abs(prevstr1 - prevstr2));
        n--;
    }
    cout << (prevstr1 && prevstr2 ? result : -1) << endl;
    return 0;
}

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

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