方块 电1面跪经

刚面完的方块公司电面， 1h， 三姐，大概有30%说的话都听不清，全程我都在ha? can u repeat?
题目很简单：给一个list of string和一个string，判断能不能从list拿出俩个来组成这个string，在这个list里有可能有重复的string出现，比如[“Apple”, "pie", "Apple"] 那么 “Applepie” 和"AppleApple"都应该返回true，list里的string每个只能用一次。
我就写了个map存了list，value放了count，然后iterate over string的index，切两半判断一下左右俩能不能行map里有没有，要处理一下左右一样的情况。
我大概说了下思路三姐就问复杂度了，问了算不算substring的co

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

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

神知道优化做法求告知呀。
sq一直对代码要求比较高，感觉题目不难最后踩点写完跑过， 但是疙里疙瘩代码也不够整洁的，也是稳跪无疑了

求！大！米！

他家面试可以自选语言吗？ 还是只能用JAVA？

Emma_Emma 发表于 2019-2-1 10:47
他家面试可以自选语言吗？ 还是只能用JAVA？

可以自选的

看到需要前缀搜索的题，
一个常见并且此题可行的优化的做法是 list of strings 做 trie 然后在string上dfs
之后list不长的情况下可以考虑可以做memo剪枝优化或者dp[sublist][substring]
还可以根据input长度加些小逻辑继续优化剪枝，比如list of strings全长小于string长度可以剪，list of strings不含string中某个char可以剪等等。
是一道发挥空间很大的题哈哈。

但build一个trie的时间再dfs面试时间不太够吧

robinbach 发表于 2019-2-28 22:30
看到需要前缀搜索的题，
一个常见并且此题可行的优化的做法是 list of strings 做 trie 然后在string上dfs ...

list of string做trie, 如果List中有重复的string, 并且每一个string只能使用一次呢？在Build trie的时候应该怎么修改啊