Airbnb 电面难题

漫漫人生路 发表于 2019/09/17 07:21:37
楼主，请问，其实是不是把所有可能情况用trie存起来啊？
麻烦您看下我理解的对不对？
原字符串abcde
与abcde 相差一个字符的pattern且以a开头的为以下四种（_代表相差字符）
a...

不对，还是character

匿名函数 发表于 2019-9-17 07:25
不对，还是character

如果还是character的话，那么一个长度为k的字符串，有k个pattern，
每个pattern中的k字符要逐个放进trie里， 那么n个字符串，时间复杂度应该是O（n*k^2）吧？

请问为什么不能直接把所有N*K种用_替代一个char的string存到一个hashset里，判断N*K次这个string （e.g. ab_d)有没有在这个hashset里，这样一共space是O(NK), time是O(NK)（判断NK次，每次判断ab_d在不在hashset里O(1))

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

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

codeforliving 发表于 2019-9-15 15:41
N个字符串，每个字符串最多生成K个有且只有一个空格的字符串，总共难道不应该是NK个这样的字符串插入到hash ...

因为插入是NK, 最后你比较时又是K,  所以是NKK

请问lz这一提需要返回什么呢，是指返回true or false们，还是要返回所有的字符串组合？

mrno5zzz 发表于 2019/09/15 13:27:13
这个直接扫一遍建一个trie，然后再扫一遍，用trie判断是不是满足有且仅有一个char match不上就好了吧，不需要俩trie吧

同问 zszszszs紫薯

tm1234 发表于 2019/10/26 05:03:10
请问lz这一提需要返回什么呢，是指返回true or false们，还是要返回所有的字符串组合？

true false

匿名函数 发表于 2019/10/26 20:50:06
true false

多谢！zszszszszs