S*******C
发帖数: 822 | 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。在他的提示下我给了暴力做法。小哥不断给支
持和鼓励。最后时间不多了
代码写了个大概，小哥就让问问题了。 |
S*******C
发帖数: 822 | |
S*******C
发帖数: 822 | |
S*******C
发帖数: 822 | 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分。。 |
S*******C
发帖数: 822 | 5 is_word可以直接判断某个string是不是word，返回boolean。思路就是在playboard中
以遍历，以某一character作为起点，往外扩散增加string长度，对所有的string都用
is_word检查。注意不能超出board边界，并且不能重复访问同一点 |
S*******C
发帖数: 822 | 6 is_word可以直接判断某个string是不是word，返回boolean。思路就是在playboard中
以遍历，以某一character作为起点，往外扩散增加string长度，对所有的string都用
is_word检查。注意不能超出board边界，并且不能重复访问同一点 |
x********u
发帖数: 1061 | 7 hash效率更高
奇怪为啥题目要说明是3X3？和1X9不是没区别么，都是九个character随意组合。 |
S*******C
发帖数: 822 | 8 把所有的word都hash？
【在 x********u 的大作中提到】
: hash效率更高
: 奇怪为啥题目要说明是3X3？和1X9不是没区别么，都是九个character随意组合。
|
c*******0
发帖数: 162 | 9 对字典里所有词建立prefix tree，然后用这题https://leetcode.com/problems/word-
search/同样的方法scan matrix。 |
S*******C
发帖数: 822 | 10 这样都没有调用ispresent()方法，应该不是最优解
word-
【在 c*******0 的大作中提到】
: 对字典里所有词建立prefix tree，然后用这题https://leetcode.com/problems/word-
: search/同样的方法scan matrix。
|
x********u
发帖数: 1061 | 11 是的，字典里所有word都hash一遍不过是O(n)嘛
【在 S*******C 的大作中提到】
: 把所有的word都hash？
|
l***i
发帖数: 1309 | 12 an easier version of boggle (4x4)
dfs with recursion. |
