Lyft店面一題

今天店面Lyft一題,有點愣住,完全沒有頭緒,最後沒解出來就時間到了

給一個二維char array,和一個Dictionary API,裡面有一個 method: bool IsValidWord

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

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

實在想不出有其他方法,
有稍微提到Trie,但這個情況我並不認為能優化多少,所以最後就用暴力DFS解,沒寫完就到時了

求解任何更好的方法

占个沙发 楼主是第几轮？呢

这道题目是212的变形。212用trie是把dictionary存起来，但是这个题目没法存dictionary.

补充内容 (2018-8-3 23:21):
所以确实是只能用dfs吧。是不是因为面试官觉得word search ii都写出来太复杂了，所以让你解决一个简化版。

trie即使输入half word也可以知道是不是在里面 比如density 你输入den 这个只有输入完整词才可以 不遍历完你就不知道是不是找完了

楼主的暴力dfs如何terminate？每个点都遍历一次吗？

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

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

暴力 + cache?

这个题就是word search2啊

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

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

ld_xixi 发表于 2018-8-7 03:40
这个题就是word search2啊

但是沒有給字典裡的字沒辦法建Trie啊