当前位置: 首页 > article >正文

每日一题---数组中两个字符串的最小距离

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

给定一个字符串数组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说明没找到
    }
}


http://www.kler.cn/a/587784.html

相关文章:

  • 【架构差异】SpringとSpringBoot:Bean机制的深入剖析与自动配置原理
  • 多页pdf转长图
  • Elasticsearch Java High Level Client [7.17] 使用
  • kettle的转换中sql不按设计顺序执行原因分析与解决办法
  • 【Godot】检查器的作用
  • 苹果iOS 18.4将强制升级HomeKit架构,旧版设备或无法使用
  • JVM之Arthas的jvm命令
  • 使用Python和Keras库实现基于双向门控循环单元(BiGRU)模型进行深度学习序列预测的示例
  • AGI大模型(6):提示词模型进阶
  • UE5 控件反射器查找源码方法
  • 谈谈List,Set,Map的区别
  • vscode 中打开ESP-IDF插件的欢迎页面
  • 前端面试笔试
  • Devops CI/CD
  • 【数据结构C语言】一、基本概念
  • 文件解析漏洞靶场解析全集详解
  • 数据库系统概念全面解析
  • 前端如何实现生成excel文件,并下载
  • 优化GreatSQL日志文件空间占用
  • vue3实现跨页面缓存