求牛人指点a家面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求牛人指点a家面试题

求牛人指点a家面试题# JobHunting - 待字闺中

c*02013-10-26 07:10

1 楼

给一个n*n的矩阵，每个元素是一个字母，元素有可能是重复的，给你一个很大的字典
，和一堆要找的单词有长有短，找的时候只能上下左右移动，问如何快速度的找出来
所有单词？
有什么高级算法吗？求指点
[发表自未名空间手机版 - m.mitbbs.com]

f*s2013-10-26 07:10

2 楼

请看leetcode原题word search

c*g2013-10-26 07:10

3 楼

Prefix tree

给一个n*n的矩阵，每个元素是一个字母，元素有可能是重复的，给你一个很大的字典
，和一堆要找的单词有长有短，找的时候只能上下左右移动，问如何快速度的找出来
所有单词？有什么高级算........

【在 c***0 的大作中提到】

: 给一个n*n的矩阵，每个元素是一个字母，元素有可能是重复的，给你一个很大的字典
: ，和一堆要找的单词有长有短，找的时候只能上下左右移动，问如何快速度的找出来
: 所有单词？
: 有什么高级算法吗？求指点
: [发表自未名空间手机版 - m.mitbbs.com]

c*02013-10-26 07:10

4 楼

谢牛人

[发表自未名空间手机版 - m.mitbbs.com]

【在 f**********s 的大作中提到】

: 请看leetcode原题word search

s*u2013-10-26 07:10

5 楼

没看懂lz的意思，你既有矩阵，又有词典，又要找单词。那是说从词典里找单词，还是
矩阵里找？?
如果有一个大词典，然后从矩阵里找词典里的词，那么就是boggle game，用词典建立
trie，然后用回溯来遍历矩阵。
如果说是没有词典，只有一个矩阵，从矩阵里找一个单词的路径，那么就是word
search，应该是不用trie的。leetcode：word search

【在 c***0 的大作中提到】

: 谢牛人
:
: [发表自未名空间手机版 - m.mitbbs.com]