我刚刚看到这个问题,除了暴力搜索,我想不到更好的方法。题目描述如下:给定一个二维字符数组和一个有效单词列表。 1)在数组中找出所有有效单词。从数组中的每个元素开始,你可以向上、向下、向右或向左遍历。 例如:
g o d b o d y
t a m o p r n
u i r u s m p
上述2D数组中的有效单词->god,goat,godbody,amour等。
我刚刚看到这个问题,除了暴力搜索,我想不到更好的方法。题目描述如下:给定一个二维字符数组和一个有效单词列表。 1)在数组中找出所有有效单词。从数组中的每个元素开始,你可以向上、向下、向右或向左遍历。 例如:
g o d b o d y
t a m o p r n
u i r u s m p
RecursiveMatch(i,j,wordPart)
if ((i,j,wordPart) in cache)
print cache[i,j,wordPart]
return;
if a[i,j] on the prefixTreePath){
cache[i,j,wordPart]+=RecursiveMatch(i+1,j,wordPart[1:])
cache[i,j,wordPart]+=RecursiveMatch(i-1,j,wordPart[1:])
cache[i,j,wordPart]+=RecursiveMatch(i,j+1,wordPart[1:])
cache[i,j,wordPart]+=RecursiveMatch(i,j-1,wordPart[1:])
print cache[i,j,wordPart]
}
我还没有添加任何结束情况,例如边框,这很容易添加。 我的意图是给你一个大致的想法。
public List<String> getWords(char[][] input, int x, int y, List<String> result, String current){
if(isValidWord(current))
result.add(current);
if(isValidStartOfWord(current)){
// call getWords recursively for all valid directions, concatenating the char to current
}
return result;
}
一种算法依赖于一种称为前缀树或树的合适数据结构。
第一步是预处理您的有效单词字典并将它们放入trie中。 这使您能够高效地回答这样的问题:
给定的前缀是否是有效前缀?
使用trie,您可以在O(前缀长度)
时间内回答此问题。
然后假设您已选择了一个单词的起始方块。现在需要沿着4个方向遍历网格,并检查迄今为止获得的前缀是否是有效前缀。如果不是,则不会在此方向上进一步遍历。另一方面,如果到目前为止的前缀是有效单词,则可以直接打印出来。 遍历可以使用DFS或BFS进行(实际上并不重要)。 重要的是要使用trie快速检查有效前缀和有效单词。