单词搜索2(算法)
输入:
words = ['oath, 'pea', 'eat', 'rain']
and
board = [
['o', 'a', 'a', 'n'],
['e', 't', 'a', 'e'],
['i', 'h', 'k', 'r'],
['i', 'f', 'l', 'v']]
输出:
['eat', 'oath']
1.DFS; 2.Trie
python
dx
= [-1, 1, 0, 0]
dy
= [0, 0, -1, 1]
END_OF_WORD
= '#'
class Solution(object):
def findWords(self
, board
, words
):
if not board
or not board
[0]: return []
if not words
: return []
self
.result
= set()
root
= collections
.defaultdict
()
for word
in words
:
node
= root
for char
in word
:
node
= node
.setdefault
(char
, collections
.defaultdict
())
node
[END_OF_WORD
] = END_OF_WORD
self
.m
, self
.n
= len(board
), len(board
[0])
for i
in xrange(self
.m
):
for j
in xrange(self
.n
):
if board
[i
][j
] in root
:
self
._dfs
(board
, i
, j
, '', root
)
def _dfs(self
, board
, i
, j
, cur_word
, cur_dict
):
cur_word
+= board
[i
][j
]
cur_dict
= cur_dict
[board
[i
][j
]]
if END_OF_WORD
in cur_dict
:
self
.result
.add
(cur_word
)
tmp
, board
[i
][j
] = board
[i
][j
], '@'
for k
in xrange(4):
x
, y
= i
+ dx
[k
], j
+ dy
[k
]
if 0 <= x
< self
.m
and 0 <= y
< self
.n
and board
[x
][y
] != '@' and board
[x
][y
] in cur_dict
:
self
._dfs
(board
, x
, y
, cur_word
, cur_dict
)
board
[i
][j
] = tmp
java
public class Solution {
Set
<String> res
= new HaskSet<String>();
public List
<String> findWords(char[][] board
, String
[] words
) {
Trie trie
= new Trie();
for (String word
: words
) {
trie
.insert(word
);
}
int m
= board
.length
;
int n
= board
[0].length
;
boolean[][] visited
= new boolean[m
][n
];
for (int i
= 0; i
< m
; i
++) {
for (int j
= 0; j
< n
; j
++) {
dfs(board
, visited
, "", i
, j
, trie
);
}
}
return new ArrayList<String>(res
);
}
public void dfs(char[][] board
, boolean[][] visited
, String str
, int x
, int y
, Trie trie
) {
if (x
< 0 || x
>= board
.length
|| y
< 0 || y
>= board
[0].length
) return;
if (visited
[x
][y
]) return;
str
+= board
[x
][y
];
if (!trie
.startsWith(str
)) return;
if (trie
.search(str
)) {
res
.add(str
);
}
visited
[x
][y
] = true;
dfs(board
, visited
, str
, x
- 1, y
, trie
);
dfs(board
, visited
, str
, x
+ 1, y
, trie
);
dfs(board
, visited
, str
, x
, y
- 1, trie
);
dfs(board
, visited
, str
, x
, y
+ 1, trie
);
visited
[x
][y
] = false;
}
}
