avatar
amazon 面筋题怎么做?# JobHunting - 待字闺中
S*C
1
最后20分钟左右做题:
Given a 3 by 3 array filled with single character, and a dictionary, print
out all the words the given characters can form
that are valid in the dictionary. Words can be different lengths. Dictionary
有一个function: ispresent().
LZ背景弱 对于没见过的题目无法直接想到方法。小哥给提示,说你先想2 by 2 array
。我就跟他说暴力方法。他说
对,you are on the right direction。在他的提示下我给了暴力做法。小哥不断给支
持和鼓励。最后时间不多了
代码写了个大概,小哥就让问问题了。
avatar
S*C
4
题目是letter playboard,让找word。Leetcode上的题(word search,不一样的是对角
线也可以),不过这次是要在dictionary里面找,我说那我从dictionary里面拿一个
word在board里面找,一直找到dict结尾。先要跟他说思。做完之后follow-up,如果
dictionary是1million 大小怎么办。。。完全不知道。。只能说因为playboard比较小
,可以根据一些不存在的character来减小dictionary搜索范围。之后他写如果提供is_
word(word)这个function可以判断单词是否在dictionary里面存在,怎么写。我说基本
思路差不多,改一下就行,他说那你改吧。。。我就一点一点改。。中间word.push_
back(character)只记得push忘了remove,然后被指出来了(这时候才想起来是DFS,之
前一直只说了DP),改了。。他说可以了。。然后时间就到了,结束的时候55分。。
avatar
S*C
5
is_word可以直接判断某个string是不是word,返回boolean。思路就是在playboard中
以遍历,以某一character作为起点,往外扩散增加string长度,对所有的string都用
is_word检查。注意不能超出board边界,并且不能重复访问同一点
avatar
S*C
6
is_word可以直接判断某个string是不是word,返回boolean。思路就是在playboard中
以遍历,以某一character作为起点,往外扩散增加string长度,对所有的string都用
is_word检查。注意不能超出board边界,并且不能重复访问同一点
avatar
x*u
7
hash效率更高
奇怪为啥题目要说明是3X3?和1X9不是没区别么,都是九个character随意组合。
avatar
S*C
8
把所有的word都hash?

【在 x********u 的大作中提到】
: hash效率更高
: 奇怪为啥题目要说明是3X3?和1X9不是没区别么,都是九个character随意组合。

avatar
S*C
10
这样都没有调用ispresent()方法,应该不是最优解

word-

【在 c*******0 的大作中提到】
: 对字典里所有词建立prefix tree,然后用这题https://leetcode.com/problems/word-
: search/同样的方法scan matrix。

avatar
x*u
11
是的,字典里所有word都hash一遍不过是O(n)嘛

【在 S*******C 的大作中提到】
: 把所有的word都hash?
avatar
l*i
12
an easier version of boggle (4x4)
dfs with recursion.
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。