一道字符串按顺序出现在另一字符串面试问题。。。

一个人反馈的题目是这个：
给你两个string，问第一个字符串的所有character是否能在第二个string中找到，第一个字符串的string需要在第二个字符串中按顺序出现。比如str1 = "def", str2 = "acdjhekinf", str3 = "ankjemnfknd"，str1在str2中出现而不在str3中出现。此外问了延伸的问题，比如这个问题如何实现O(n2)时间复杂度，如果str1是一堆string算法如何改进，如果数据量太大是否可以多线‍‍‍‌‌‌‍‌‌‌‌‍‌‌‍‌‌‌‍‌程计算。

不太明白str3是什么意思？比较str1和str2用双指针可以吗？比较两次一次和str2比，一次和str3比，可否？蠡口有类似题目吗？求解惑，谢谢！

DTMTouring 发表于 2022-09-25 16:41:34
老哥能否以下面这个例子详细说说，思考了好一会没看懂你写的。

str1 = ‘defde’

这题的follow up不是让你用同一个str去匹配多个字符串 而是用多个字符串去匹配同一个string。比如用abcd,adbc,acbd 去匹配abcdefsaerbda。要得出true，false，true来。

跟戚鎏很像～

这个听起来是图钉的题。比较两个字符串可以用双指针。但是如果要重复对比应该是考indexing。我当年给的方案是对每个位置标记所有下一个字符的位置。那么对当前位置只要O（1）就能拿到下一任意字符的位置。比如“abcdcba“,初始位置index=-1对abcd分别为0，1，2，3.对index=0，则为6，1，2，，3。以此类推。那没检测一次就是O（N）。我是面瓜了的，只供参考。

听说地里有黄金 发表于 2022-09-25 14:48:41
这个听起来是图钉的题。比较两个字符串可以用双指针。但是如果要重复对比应该是考indexing。我当年给的方案是对每个位置标记所有下一个字符的位置。那么对当前位置只要O（1）就能拿到下一任意字符的位置。

老哥能否以下面这个例子详细说说，思考了好一会没看懂你写的。

str1 = ‘defde’
str2 = ‘asdsegfrdqe’

这题的关键是在str1是很多str的时候 你要提前pre process str2 str3 这样就不需要每次都一个字符一个字符的循环str2和3了

我没有鳄梨回你私信，leetcode 128的变种，只不过把条件从+1变成了num ^ 2

DTMTouring 发表于 2022-9-25 19:41
老哥能否以下面这个例子详细说说，思考了好一会没看懂你写的。

str1 = ‘defde’

我没有鳄梨回你私信，leetcode 128的变种，只不过把条件从+1变成了num ^ 2

阿略 发表于 2022-09-26 16:57:37
我没有鳄梨回你私信，leetcode 128的变种，只不过把条件从+1变成了num ^ 2

谢谢老哥！！！！！！

这是leetcode的题的follow up，用dynamic programming好像