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

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

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

输出

备注:

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

算法知识视频讲解

怜弦月几许

发表于 2024-04-19 13:05:17

#include <iostream> #include <string> #include <climits> using namespace std; int main() { int n; string s1, s2, s; ci 展开全文

uzzzz~

发表于 2022-03-16 11:56:34

思路：双指针记录str1,str2的位置，遍历数组更新结果。 #include <iostream> #include <string> #include <stack> using namespace std; class mystack{ privat 展开全文

Surtr1

发表于 2024-04-23 17:13:39

#include <iostream> #include<algorithm> using namespace std; const int N =1e5+10; string strs[N]; int main() { int n; cin>> 展开全文

翁佳明

发表于 2024-04-23 19:34:55

思路：贪心 1.如果暴力：两层for循环枚举，数据范围是10^5,会超时 2.用贪心（dp）来优化 3.用若干个变量来标记某个位置前驱的最优解（常用优化方法）预处理思想只管左边，不管右边。当遍历到后面的时候，向左看，会包含之前右边的情况。 4.prev1:标记的是遍历到i位置时，左边最近符合要展开全文