面试题

发表于 2012-10-24 07:26

如题某世界知名IT企业面试题：
一个表N行，M列，每个表格中存放一个字母，每个字母可以与相邻（上下左右，左上左下右上右下）的字母组合，按照组合的顺序组成一个单词，当然选过字母的表格是不能再选择的，单词包含的字母也不限制。
如果是否能组成单词我用函数isword（）表示的话，求这个表中可以组成多少个单词。
其本质就是在一个表中画一条有方向的线，如果这条线穿过的表格内容，按照线方向排序的话可以组成单词，那么就是成功的，那么就累积这个成功的次数，这个成功的次数也就是组成单词的个数

发表于 2012-10-24 07:39

深度优先搜索吧

发表于 2012-10-24 07:54

广度优先搜索，
维护一个队列，分别对八个方向的单词进行试探。
不过复杂度貌似有点高，楼主说的画线没明白，估计我理解错题意了，是任意方向都可以组合吧

面试题

相关帖子

浏览过的版块