Airbnb 店面

给定一个N*N的board，每个位置上有一个字母，给定一个dictionary，里面有一些word。求打印可以从board里面找到的最多且在dictionary里面的word。
*在board里面找word时，只能朝上下左右四

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

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

S", "P"
     };
最多可以找到3个word，他们是EGO,SNO和NC。

谢谢分享，应该是尔幺尔，有要求一定要用tire树做吗

嗯，是尔幺尔，没要求非要用trie，可以先写出来再优化

wwx_27 发表于 2021-3-26 13:28
谢谢分享，应该是尔幺尔，有要求一定要用tire树做吗

不好意思，我再看了下刷题网上的题目，店面那道题要求一个字母如果在一个单词使用过了，那么其它单词就不能再用了。这点是不一样的。

请问每个字母最多用一次的话怎么找出现最多的？用dp吗？

July09 发表于 2021-3-27 01:18
不好意思，我再看了下刷题网上的题目，店面那道题要求一个字母如果在一个单词使用过了，那么其它单词就不 ...

感谢楼主！！

如果是要求最多的词，应该是用backtracking吧，对每一个单词，如果能找到，两个情况，用或者不用这个单词然后递归。所以是O(2^N)复杂度。
如果可以加memo来优化或者用dp，应该存什么呢?

jimmypengry2016 发表于 2021-4-18 14:18
如果是要求最多的词，应该是用backtracking吧，对每一个单词，如果能找到，两个情况，用或者不用这个单词然 ...

不要看到什么题就往leetcode的原题上套。这种题不可能多项式DP的，不满足"无后效性"这个条件(单词的方向七拐八绕，你无法build a DAG to represent DP states)

请问LZ面的什么level呢