讨论两个面经题

wisdompeak2 发表于 2021-03-25 12:08:58
你说的原贴是哪一个？有代码吗，我来看看。如果你说的是楼主发的那一层，那么看一下这个例子：
s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaad"
p = "*aaaaaaaaa

这个例子就是strstr 用kmp或者rk都可以平均O（n）

你说的这部分跟wildcard没关系 只是pattern matching

补充内容 (2021-03-26 04:08 +08:00):
我原贴的意思就是这题跟wildcard matching不一样 因为这个是match substring

Smilenceyu 发表于 2021-3-26 03:39
这个例子就是strstr 用kmp或者rk都可以平均O（n）

你说的这部分跟wildcard没关系 只是pattern matching

OK，看懂了，原来你说的贪心是指拆成若干个KMP去做。

Smilenceyu 发表于 2021-3-26 03:39
这个例子就是strstr 用kmp或者rk都可以平均O（n）

你说的这部分跟wildcard没关系 只是pattern matching

KMP就不必了，像KMP，manacher，还有什么高级图论算法， 面试官都不一定会写的，不会考的

Augustus 发表于 2021-2-3 14:08
第二题只能用高斯消元法吧，递归是解不出来的

不会考高斯消元的，面试自己都不一定会写

itaymaoz 发表于 2021-03-25 16:16:26
KMP就不必了，像KMP，manacher，还有什么高级图论算法， 面试官都不一定会写的，不会考的

robinkarp很简单 没必要kmp

补充内容 (2021-03-26 07:25 +08:00):
具体这个题面试的时候strstr用library就行了

wisdompeak2 发表于 2021-03-25 13:22:59
OK，看懂了，原来你说的贪心是指拆成若干个KMP去做。

对 反正就是strstr吧 无论你strstr用什么办法 在这个基础上贪心 而原题是必须要dp 或者 backtracking做的

Smilenceyu 发表于 2021-3-26 07:23
robinkarp很简单 没必要kmp

补充内容 (2021-03-26 07:25 +08:00):

wildcart怎么strstr?

Smilenceyu 发表于 2021-3-26 07:24
对 反正就是strstr吧 无论你strstr用什么办法 在这个基础上贪心 而原题是必须要dp 或者 backtracking做的

哦你是说遇到*之后，可以用strstr来解决接下来的字母序列的匹配

这题好像是要找s和p match的最小起始index，是不是只能把s的每个substring(i, n)都跟p做一遍match

itaymaoz 发表于 2021-03-25 17:06:56
哦你是说遇到*之后，可以用strstr来解决接下来的字母序列的匹配

对 因为这题跟leetcode那个不一样