确实karat

recruiter reach out的就随便面面练练手。五选二选了Production issues和OOD，后面的题目貌似是个新题，翻了前面几个面经没发现。题目大概是给了一个list of strings，每

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

nter比较letter，时间复杂度是O(kn^2)，k是word length，最后没想出更优的解法，也没有时间做第三题了。

想问下lz 过了吗
这个stepword感觉挺难
我觉得Tire是可以的， 当我们处理长度为n的word时 去搜索n+1的所有word，其中n+1的所有word已经构建好了Tire
当遇到不匹配的字符就cnt++ 并且skip这个字符  然后这时候使用dfs对后面的继续匹配，如果全匹配就肯定是一个结果 如果再有不匹配的那就剪枝掉了

可不可以针对这个字符串，算出所有可能的step word, 然后直接在map里面找匹配呢

算出所有可能的step word 的复杂度是 (k + 1)* 26 (k是字符串长度，每个字符的位置前面插入一个新字符，然后最后一位之后也加一个)
map里面找匹配是复杂度是1
一共是n个字符串

k*26*n 会不会好一点

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题是trietree search prefix?

wensixing1989 发表于 2022-5-7 22:09
第二题是trietree search prefix?

可以在任意位置加一个character，所以应该不是prefix

wensixing1989 发表于 2022-5-8 00:44
可不可以针对这个字符串，算出所有可能的step word, 然后直接在map里面找匹配呢

算出所有可能的step wor ...

恩，这应该是个优化

匿名者 发表于 2022-5-8 11:12
恩，这应该是个优化

space complexity 有什么要求吗

可以用int array来记录每个字母出现的次数，step word的array map与word的array map的差值必定为1，只要遍历一遍所有word就行，O(m,n), m是word数量，n是单个字符串长度

匿名者 发表于 2022-5-9 13:08
space complexity 有什么要求吗

没有要求

uscbob2020 发表于 2022-5-11 22:26
可以用int array来记录每个字母出现的次数，step word的array map与word的array map的差值必定为1，只要遍 ...

你这个是找一个word的step words吧？题目是要找所有的words