h****b
发帖数: 25 | 1 一个amazon的算法题描述如下（在以前的面经里面看到的）：
boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
这个题目感觉下code的话很难写的啊？ 如何用DFS或者递归的话 如何避免访问重发的
元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？ 感觉DFS找一个valid word
比较容易， 找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了 。。 | g***y
发帖数: 764 | 2 递归 和DFS没什么关系
word
【在 h****b 的大作中提到】
: 一个amazon的算法题描述如下（在以前的面经里面看到的）：
: boggle游戏的问题：给定一个4*4的矩阵，每个
: 位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
: 已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
: 这个题目感觉下code的话很难写的啊？ 如何用DFS或者递归的话 如何避免访问重发的
: 元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？ 感觉DFS找一个valid word
: 比较容易， 找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了 。。
| R***i
发帖数: 78 | 3 My solution:
prefix tree to store all words in dictionary
for each cell in matrix
do BFS
add to BFS queue only if partial_word can be found in prefix tree and
unvisited
O(n^2) solution, may not be optimal, but guarantee to work. | g*****k
发帖数: 623 | 4 个人感觉这就是纯递归的算法题
word
【在 h****b 的大作中提到】
: 一个amazon的算法题描述如下（在以前的面经里面看到的）：
: boggle游戏的问题：给定一个4*4的矩阵，每个
: 位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
: 已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
: 这个题目感觉下code的话很难写的啊？ 如何用DFS或者递归的话 如何避免访问重发的
: 元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？ 感觉DFS找一个valid word
: 比较容易， 找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了 。。
| b********n
发帖数: 29 | 5 #define N 4
void FindWordsBoggle(char board[][N])
{
int i=0,j=0;
char* outStr = (char*) malloc((N*N+1)*sizeof(char));
int* occupMap = (int*) calloc((N*N),sizeof(int));
int level = 0;
RecursiveBoggle(board, outStr, level, occupMap);
free(occupMap);
free(outStr);
}
void RecursiveBoggle(char board[][N], char* outStr, int level, int*
occupMap)
{
int* occupMapCopy = (int*) malloc((N*N)*sizeof(int));
memcpy(occupMapCopy, occupMap, N*N*sizeof(int));
int i=0,j=0;
for ( ; i < N; i++)
{
for (; j < N; j++)
{
if (!occupMapCopy[i*N+j])
{
outStr[level] = board[i][j];
outStr[level+1] = '\0';
/*Find whether the current string is available as a word.*/
if (FindInDictionary(outStr))
printf("%s\n",outStr);
if (FindPrefixInDictionary(outStr))
{
occupMapCopy[i*N+j] = 2;
/*Label neighbors as traversable*/
LabelNeighbors(occupMapCopy, i, j);
RecursiveBoggle(board, outStr, level+1, occupMapCopy);
}
}
}
}
free(occupMapCopy);
}
void LabelNeighbors(int* occupMap, int i, int j)
{
int ii=0,jj=0;
for (; ii < N; ++ii)
{
for (; jj < N; ++jj)
{
if (occupMap[ii*N+jj] == 2)
/*already used*/
continue;
else if ( abs(ii-i) <=1 && abs(jj-j) <=1 )
/*can be next character*/
occupMap[ii*N+jj] = 0;
else occupMap[ii*N+jj] = 1; /*not reachable*/
}
}
} | s********y
发帖数: 161 | 6 建议学习programming interview expose里的递归章节，练习一下permutation,
combination, coin change, integer partition，这一类的题(本质上是DFS搜索穷举)
你就没问题了。 | f***g
发帖数: 214 | 7 这个题递归是没错的。
关键在于字典的结构。
用trie可以在第一时间内判断has_prefix()
然后剪纸 |
|
