【牛客】两个字符串之间的最短距离

🎗️ 主页：小夜时雨
🎗️专栏：算法题
🎗️如何活着，是我找寻的方向

1. 题目解析

题目链接: https://www.nowcoder.com/practice/2c6a0a8e1d20492f92941400036e0890

本道题是个模版, 还有一系列相关的问题: 比如

• 给一个整数数组, 求两个数字之间的最短距离
• 给一个字符串, 求两个字符在字符串中的最短距离
• 给一个字符串数组, 求两个字符串在字符串数组中的最短距离

本道题就属于是第三种, 输入多个字符串, 也就相当于是一个字符串数组.

暴力枚举思路：

1. 首先想到的就是暴力枚举, 遍历完所有的情况, 找到最短的距离.
2. 固定一个下标 i , 另一个下标 j 从 i 位置出发, 向后遍历所有的情况. 找到两个字符串, 用 ret 变量记录二者的距离: 下标相减即可.
3. i 向后移动, j 继续从 i 位置出发, 遇到符合条件的, 就用 ret 来更新结果.
4. 全部遍历完, ret 也更新完毕. 此时 ret 就是答案.
5. 细节点: 因为找的是最短距离, 所以可以把 ret 初始化为无穷大, 这样就不会影响结果. 假如初始化为 0, 找的是最小值, 有可能把 0 当做最后的结果了, 其实 0 不是结果.

暴力枚举的时间复杂度: 两个 for 循环, 时间复杂度就是 O(N ^ 2), 测试的话会超时, 但是往往暴力枚举能给我们提供思路, 接下来介绍一种贪心优化.

贪心优化:

1. 我们拿两个指针记录前面我们遍历过的 str1 和 str2 的位置. 这样我们就不用回去进行再次遍历一遍. 假如回去往前再遍历一遍就和暴力枚举一样了, 只不过是遍历一个数前面的所有可能.
2. 然后 i 遍历这个字符串数组, 假如第 i 个正好是 str1, 那么我们就去找前面的 str2, 这个距离就是此时的最近的. str2呢 正好我们用指针来记录位置了, 所以 ret 就是更新为 i - str2 的下标. 遇到 str2 同理, 去找前面的 str1.
3. 然后 i 继续遍历, ret 符合条件的就更新. 这样只需遍历一遍数组即可找出最短距离.

接下来的代码里还会再次进行强调的，看下面的图更容易理解：

2. 代码

看下面的代码对照着上面的流程解析可能会更加的清楚。

   import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();String s1 = in.next(), s2 = in.next();// prev1 标记前面 s1 出现的最近的下标// 同理, prev2 标记前面 s2 出现的最近的下标int prev1 = -1, prev2 = -1, ret = 0x3f3f3f3f;for (int i = 0; i < n; i++) {String s = in.next();// 进行更新, 去找前面的 s2if (s.equals(s1)) {if (prev2 != -1) {// 进行更新ret = Math.min(ret, i - prev2);}// s1 出现了一次, 进行更新prev1 = i;} else if (s.equals(s2)) {// 去找前面的 s1if (prev1 != -1) {// 进行更新ret = Math.min(ret, i - prev1);}// s2 又出现了一次, 进行更新prev2 = i;}}System.out.println(ret == 0x3f3f3f3f ? -1 : ret);}
}

🎗️🎗️🎗️ 好啦，到这里有关本题的分享就没了，如果感觉做的还不错的话可以点个赞，关注一下，你的支持就是我继续下去的动力，我们下期再见，拜了个拜~ ☆*: .｡. o(≧▽≦)o .｡.:*☆