数组中两个字符串的最小距离
给定一个字符串数组strs,再给定两个字符串str1和str2,返回在strs中str1和str2的最小距离,如果str1或str2为null,或不在strs中,返回-1。
链接:数组中两个字符串的最小距离__牛客网
来源:牛客网
输入描述:
输入包含有多行,第一输入一个整数n(1≤n≤105)(1 \leq n \leq 10^5)(1≤n≤105),代表数组strs的长度,第二行有两个字符串分别代表str1和str2,接下来n行,每行一个字符串,代表数组strs (保证题目中出现的所有字符串长度均小于等于10)。
输出描述:
输出一行,包含一个整数,代表返回的值。
示例1:
输入
1
CD AB
CD
输出
-1
示例2:
输入
5
QWER 666
QWER
1234
qwe
666
QWER
输出
1
备注:
时间复杂度O(n)O(n),额外空间复杂度O(1)O(1)
解题:
解法一:暴力解法
可以定义两层for循环,i j ,当i找到一个str1时,就让j向后找最近的str2,并更新最近的距离ret,
然后让i遍历所有的字符串,得到最近距离。但这样显然超时了,不过我们可以对这个方法进行优化。
解法二:模拟
优化的方法有很多,比如可以先循环一遍找到所有的str1,str2并把下标记录下来,然后对这两个下标数组找最小距离,但这样空间复杂度就高了。
不妨在读取字符串的时候尝试用两个单独的数字prev1,prev2记录str1与str2的下标,并随着读取不断更新当前的下标。即:prev1代表当前最靠右的str1,prev2代表当前最靠右的str2,然后每次ret就更新prev1-prev2或prev1-prev2,表示向左寻找距离最近的另一个字符串,由于读取是向右读取的,这样就可以遍历到全部的情况
代码如下:
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();in.nextLine();String str1 = in.next();String str2 = in.next();int prev1 = -1;//str1的最靠右的下标int prev2 = -1;//str2的最靠右的下标//注意要找距离最近的,所以初始化成最大的int ret = 0x3f3f3f3f;for(int i = 0; i < n; i++) {String tmp = in.nextLine();//不用创建数组,直接在读取时更新即可if(tmp.equals(str1)) {prev1 = i;//更新str1的下标if(prev2 != -1)ret = Math.min(prev1 - prev2, ret);}if(tmp.equals(str2)) {prev2 = i;//更新str2的下标if(prev1 != -1)ret = Math.min(prev2 - prev1, ret);}}System.out.println(ret == 0x3f3f3f3f ? -1 : ret);//如果没更新ret说明没找到}
}